DOI: 10.17377/alglog.2018.57.401 |
УДК 510.52+512.563+510.67 |
П. Е. Алаев |
Категоричность для примитивно рекурсивных и полиномиальных булевых алгебр, 389—425. |
Определяется класс ${\mathbb K}_{\Sigma}$, состоящий из примитивно рекурсивных структур, в которых экзистенциальная диаграмма разрешима с примитивно рекурсивными свидетелями. Доказывается, что булева алгебра обладает представлением из ${\mathbb K}_{\Sigma}$ тогда и только тогда, когда у неё есть вычислимое представление с вычислимым множеством атомов. Кроме того, такая булева алгебра примитивно рекурсивно категорична относительно ${\mathbb K}_{\Sigma}$ тогда и только тогда, когда число атомов в ней конечно. Полученные результаты переносятся и на случай булевых алгебр, вычислимых за полиномиальное время. |
Ключевые слова: булева алгебра; булева алгебра, вычислимая за полиномиальное время; вычислимое представление; примитивно рекурсивно категоричная булева алгебра. |
Адрес автора:
Алаев Павел Евгеньевич, |
DOI: 10.17377/alglog.2018.57.402 |
УДК 510.54 |
С. А. Бадаев, А. А. Исахов |
Некоторые абсолютные свойства $A$-вычислимых нумераций, 426—447. |
Для произвольного множества натуральных чисел $A$ доказываются следующие утверждения: любое конечное семейство $A$-вычислимых множеств с наименьшим по включению элементом имеет $A$-вычислимую универсальную нумерацию; любое бесконечное $A$-вычислимое семейство всюду определенных функций имеет с точностью до $A$-эквивалентности либо одну, либо бесконечно много $A$-вычислимых фридберговых нумераций; любое $A$-вычислимое семейство всюду определенных функций, содержащее предельную функцию, не имеет $A$-вычислимых универсальных нумераций даже относительно $A$-сводимости. |
Ключевые слова: $A$-вычислимая нумерация, $A$-вычислимая фридбергова нумерация, $A$-вычислимая универсальная нумерация, $A$-сводимость. |
Адреса авторов:
Бадаев Серикжан Агыбаевич,
Казахский национальный ун-т им. аль-Фараби,
пр. аль-Фараби, 71, г. Алма-Ата, 050040, Казахстан.
e-mail: Serikzhan.Badaev@kaznu.kz |
DOI: 10.17377/alglog.2018.57.403 |
УДК 510.5 |
А. Н. Рыбалов |
О генерической амплификации рекурсивно перечислимых множеств, 448—455. |
Генерическая амплификация — это метод, который позволяет из алгоритмически неразрешимых проблем получать проблемы, неразрешимые для почти всех входов. Доказывается, что любое простое пренебрежимое множество является неразрешимым для почти всех входов, но не может быть получено с помощью амплификации из какого-либо неразрешимого множества. С другой стороны, показывается, что любое рекурсивно перечислимое множество с ненулевой асимптотической плотностью может быть получено с помощью амплификации из множества натуральных чисел. |
Ключевые слова: алгоритмически неразрешимая проблема, генерическая амплификация, неразрешимое множество, простое пренебрежимое множество, рекурсивно перечислимое множество. |
Адрес автора: Рыбалов Александр Николаевич, Ин-т матем. им. С. Л. Соболева СО РАН, ул. Певцова, 13, г. Омск, 644099, Россия. e-mail: alexander.rybalov@gmail.com |
DOI: 10.17377/alglog.2018.57.404 |
УДК 512.5 |
Е. И. Тимошенко |
О теориях относительно свободных разрешимых групп с дополнительным предикатом, 456—475. |
Изучаются элементарные и универсальные теории относительно свободных разрешимых групп в групповой сигнатуре, расширенной одним предикатом, выделяющим примитивные или аннулирующие системы элементов. |
Ключевые слова: разрешимая группа, нильпотентная группы, элементарная теория, универсальная теория. |
Адрес автора: Тимошенко Евгений Иосифович, каф. алгебры матем. логики, Новосибирский гос. техн. ун-т, пр. К. Маркса, 20, г. Новосибирск, 630092, Россия. e-mail: eitim45@gmail.com |
DOI: 10.17377/alglog.2018.57.405 |
УДК 512.540+510.5 |
А. Н. Хисамиев |
Универсальные функции и неограниченно ветвящиеся деревья, 476—491. |
Доказывается, что в наследственно конечной надстройке над неограниченно ветвящимся деревом конечной высоты существует универсальная $\Sigma$-функция. |
Ключевые слова: наследственно конечная надстройка, неограниченно ветвящееся дерево конечной высоты, универсальная $\Sigma$-функция. |
Адрес автора:
Хисамиев Асылхан Назифович, |
DOI: 10.17377/alglog.2018.57.406 |
УДК 510.5 |
И. Ш. Калимуллин, В. Г. Пузаренко, М. Х. Файзрахманов |
Позитивные представления семейств относительно сводимости по перечислимости, 492—498. |
Адреса авторов:
Калимуллин Искандер Шагитович, Казанский (Приволжский) федерал.
ун-т, ул. Кремлёвская, 18, г. Казань, 420008, Россия. e-mail:
Iskander.Kalimullin@kpfu.ru |