Теоретико вычислительные свойства структур с вложением

Изучаются теоретико вычислительные свойства вычислимых структур с вложением и сложность изоморфизмов между этими структурами. Доказывается, что вычислимая структура с вложением вычислимо категорична в том и только том случае, если у неё конечное число бесконечных орбит. Кроме того, вычислимая структура с вложением будет $\Delta^0_2$-категорична тогда и только тогда, когда у неё конечное число орбит типа $\omega$ или конечное число орбит типа $Z$. Далее, каждая вычислимо категоричная структура с вложением является относительно вычислимо категоричной, и каждая $\Delta^0_2$-категоричная структура с вложением является $\Delta^0_2$-категоричной. Рассматриваются аналоги этих результатов для $\Sigma^0_1$-, $\Pi^0_1$- и $n$-в.п. структур с вложением.
Изучается сложность множества элементов с орбитами заданного типа в вычислимых структурах с вложением. Например, доказывается, что для каждой в.п. тьюринговой степени $\mathbf b$ существует вычислимая структура с вложением $\mathcal A$, в которой множество всех элементов с конечными орбитами имеет степень $\mathbf b$, и для произвольной $\Sigma^0_2$-тьюринговой степени $\mathbf c$ существует вычислимая структура с вложением $\mathcal B$, в которой множество всех элементов с орбитами типа $\omega$ имеет степень $\mathbf c$. Доказываются также некоторые результаты об индексных множествах бесконечных вычислимых структур с вложением. Например, индексное множество бесконечной вычислимо категоричной структуры с вложением оказывается $\Sigma^0_3$-полным множеством, а индексное множество бесконечной $\Delta^0_2$-категоричной структуры с вложением – $\Sigma^0_4$-полным.
Используется связь между характером и теорией первого порядка вычислимой структуры с вложением. Показывается, что для каждой структуры с вложением, обладающей вычислимым характером, существует изоморфная ей разрешимая структура. Тем не менее, существуют вычислимо категоричные структуры с вложением, теории которых неразрешимы.