Вычислимые структурные и антиструктурные теоремы

В своем докладе в Казани в 1997 г. первый автор сформулировал ряд проблем, касающихся классификации вычислимых представителей различных классов моделей. Казалось, что некоторые проблемы могут иметь хороший ответ, в то время как другие – еще нет. По окончании указанного доклада, Шор спросил о том, что могло бы быть убедительным отрицательным ответом. Целью настоящей работы является рассмотрение некоторых возможных ответов на этот вопрос Шора. Рассматриваются модели $\mathcal A$ некоторого вычислимого языка, носители которых являются вычислимыми множествами констант. При измерении сложности $\mathcal A$ отождествляется с ее атомной диаграммой $D(\mathcal A)$, которая, с помощью геделевской нумерации, может рассматриваться как подмножество в $\omega$. В частности, $\mathcal A$ вычислима, если $D(\mathcal A)$ вычислима. Если $K$ – некоторый класс, то через $K^c$ обозначается множество вычислимых элементов из $K$. Вычислимая характеризация для $K$ должна отделять вычислимые элементы $K$ от других моделей, т. е. либо не встречающихся в $K$, либо не являющихся вычислимыми. Вычислимая классификация (или структурная теорема) должна описывать каждый элемент $K^{c}$ с точностью до изоморфизма или другой эквивалентности в терминах относительно простых инвариантов. Вычислимая антиструктурная теорема должна утверждать, что вычислимой структурной теоремы не существует. Используются три различных подхода. Все они дают “правильный” ответ для векторных пространств над $Q$ и для линейных порядков. Это означает, что при всех трех подходах для обоих классов есть вычислимая характеризация; для векторных пространств можно найти вычислимую классификацию, а для линейных порядков – нет. Формулируются открытые проблемы.