RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 2018, том 57, номер 3, страницы 338–361 (Mi al853)

Эта публикация цитируется в 3 статьях

О тьюринговых степенях в утончениях арифметической иерархии

В. Л. Селивановab, М. М. Ямалеевb

a Ин-т сист. информ. им. А. П. Ершова СО РАН, пр. Ак. Лаврентьева, 6, г. Новосибирск, 630090, РОССИЯ
b Казанский (Приволжский) федерал. ун-т, ул. Кремлёвская, 18, г. Казань, 420008, РОССИЯ

Аннотация: Исследуется задача характеризации собственных уровней тонкой иерархии (с точностью до тьюринговой эквивалентности). Известно, что тонкая иерархия исчерпывает арифметические множества и содержит в качестве малого фрагмента конечные уровни иерархий Ершова (релятивизованных относительно $\varnothing^n$, $n<\omega$), собственность которых известна. Основной результат состоит в нахождении наименьшего нового (т.е. отличного от уровней релятивизиванных иерархий Ершова) собственного уровня. Также показывается, что не все новые уровни будут собственными.

Ключевые слова: иерархия Ершова, тонкая иерархия, аримфметическая иерархия, тьюринговы степени.

УДК: 510.51+510.54+510.531+510.532

Поступило: 12.12.2016
Окончательный вариант: 20.10.2017

DOI: 10.17377/alglog.2018.57.306


 Англоязычная версия: Algebra and Logic, 2018, 57:3, 222–236

Реферативные базы данных:


© МИАН, 2024