Аннотация
Изучение автоморфизмов вычислимых и других структур является одним из связующих звеньев между теорией вычислимости и классической теорией групп. Вычислимо перечислимые структуры являются одними из наиболее важных невычислимых счётных объектов исследования в теории вычислимых моделей. Здесь внимание сфокусировано на решётке вычислимо перечислимых подструктур данной канонической вычислимой структуры. В частности, для тьюринговой степени изучаются группы -вычислимых автоморфизмов решётки -перечислимых векторных подпространств, интервальной булевой алгебры на упорядоченном множестве рациональных чисел, а также решётки -перечистимых под алгебр -Оказывается, что тьюрингова сводимость для этих групп может быть фактически заменена на вложимость групп. Кроме того, тьюрингова степень типов изоморфизма для этих групп равна второму тьюринговому скачку для множества
Язык оригинала | русский |
---|---|
Страницы (с-по) | 24-47 |
Число страниц | 21 |
Журнал | Алгебра и логика |
Том | 59 |
Номер выпуска | 1 |
DOI | |
Состояние | Опубликовано - 1 мар. 2020 |
ГРНТИ
- 27 МАТЕМАТИКА