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

Результат исследования: Научные публикации в периодических изданияхстатья

Аннотация

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

ГРНТИ

  • 27 МАТЕМАТИКА

Цитировать