DOI: 10.17377/alglog.2016.55.601 |
УДК 510.5+512+510.6 |
П. Е. Алаев |
Доказывается, что любая вычислимая локально конечная структура с конечным числом функций обладает представлением, вычислимым за полиномиальное время. Кроме того, структура, вычислимая за полиномиальное время, является полиномиально категоричной тогда и только тогда, когда она конечна. Если структура вычислима за полиномиальное время и локально конечна, то она слабо полиномиально категорична (т. е. категорична относительно примитивно рекурсивных изоморфизмов) тогда и только тогда, когда конечна. |
Ключевые слова: локально конечная структура; вычислимая структура; структура, вычислимая за полиномиальное время; полиномиально категоричная структура; слабо полиномиально категоричная структура. |
Адрес автора:
Алаев Павел Евгеньевич, |
DOI: 10.17377/alglog.2016.55.602 |
УДК 512.7 |
В. Г. Бардаков, М. В. Нещадим |
Подгруппы, автоморфизмы и алгебры Ли, связанные с группой сопрягающих базис автоморфизмов, 670—703. |
Изучаются некоторые подгруппы группы автоморфизмов свободной группы, их разложения в полупрямое произведение, группы автоморфизмов, а также присоединённые алгебры Ли. |
Ключевые слова: свободная группа, группа автоморфизмов, алгебра Ли. |
Адреса авторов:
Бардаков Валерий Георгиевич, |
DOI: 10.17377/alglog.2016.55.603 |
УДК 510.53+514.146 |
Н. Т. Когабаев |
Свободно порождённые проективные плоскости конечной вычислимой размерности, 704—737. |
Доказывается, что для любого натурального $n\geqslant 1$ существует вычислимая свободно порождённая проективная плоскость, вычислимая размерность которой равна $n$. Устанавливается, что класс свободно порождённых проективных плоскостей является полным относительно спектров степеней автоморфно нетривиальных структур, эффективных размерностей, константных расширений и спектров степеней отношений. |
Ключевые слова: проективная плоскость, свободно порождённая проективная плоскость, вычислимая структура, спектр степеней структуры, вычислимая размерность, спектр степеней отношения. |
Адрес автора:
Когабаев Нурлан Талгатович, |
DOI: 10.17377/alglog.2016.55.604 |
УДК 510.65 |
М. В. Коровина, О. В. Кудинов |
Устанавливаются необходимые и достаточные условия принадлежности степеней Тьюринга спектру классического поля вычислимых действительных чисел. |
Ключевые слова: поле вычислимых действительных чисел, степень Тьюринга. |
Адреса авторов:
Коровина Маргарита Владимировна,
Ин-т сист. информ. СО РАН,
пр. Лаврентьева, 6,
г. Новосибирск,
630090, Россия.
e-mail: rita.korovina@gmail.com |
DOI: 10.17377/alglog.2016.55.605 |
УДК 512.57 |
А. Г. Пинус |
Об алгебраически эквивалентных клонах, 760—768. |
Два функциональных клона $F$ и $G$ на множестве $A$ называются алгебраически эквивалентными, если совпадают совокупности решений на $A$ для $F$- и $G$-уравнений. Доказывается, что число попарно алгебраически не эквивалентных экзистенциально аддитивных клонов на конечных множествах $A$ конечно. Доказываются результаты о строении классов алгебраической эквивалентности, включающих в себя эквационально аддитивный клон, в решётках всех клонов на конечных множествах. |
Ключевые слова: клон, эквационально аддитивный клон, алгебраически эквивалентные клоны, решётка. |
Адрес автора: Пинус Александр Георгиевич, каф. алгебры матем. логики, Новосибирский гос. техн. ун-т, пр. К. Маркса, 20, г. Новосибирск, 630092, Россия. e-mail: ag.pinus@gmail.com |
DOI: 10.17377/alglog.2016.55.606 |
УДК 510.5 |
А. И. Стукачев |
Обобщённо гиперарифметическая вычислимость над структурами, 769—799. |
Рассматривается класс аппроксимационных пространств, порождённых допустимыми множествами и, в частности, наследственно конечными надстройками над структурами. Обобщённая вычислимость на аппроксимационных пространствах понимается как эффективная определимость в динамической логике. Аналогично понятию структуры, $\Sigma$-определимой в допустимом множестве, вводится понятие эффективной определимости структуры на аппроксимационном пространстве. Аналогично тому, как определяется отношение $\Sigma$-сводимости, естественным образом возникает отношение сводимости на структурах, порождающее соответствующие полурешётки степеней структур (произвольной мощности), а также операция скачка. Устанавливается естественное вложение в эти полурешётки полурешётки гиперстепеней множеств натуральных чисел, сохраняющее операцию гиперскачка. Даётся синтаксическое описание структур, имеющих гиперстепень. |
Ключевые слова: теория вычислимости, допустимые множества, аппроксимационные пространства, конструктивные модели, вычислимый анализ, гиперарифметическая вычислимость. |
Адрес автора:
Стукачев Алексей Ильич, |