Тьюринговы степени и группы автоморфизмов решёток подструктур

Изучение автоморфизмов вычислимых и других структур является одним из связующих звеньев между теорией вычислимости и классической теорией групп. Вычислимо перечислимые структуры являются одними из наиболее важных невычислимых счётных объектов исследования в теории вычислимых моделей. Здесь внимание сфокусировано на решётке вычислимо перечислимых подструктур данной канонической вычислимой структуры. В частности, для тьюринговой степени изучаются группы -вычислимых автоморфизмов решётки -перечислимых векторных подпространств, интервальной булевой алгебры на упорядоченном множестве рациональных чисел, а также решётки -перечистимых под алгебр -Оказывается, что тьюрингова сводимость для этих групп может быть фактически заменена на вложимость групп. Кроме того, тьюрингова степень типов изоморфизма для этих групп равна второму тьюринговому скачку для множества