|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
О тьюринговых степенях в утончениях арифметической иерархии
В. Л. Селивановab, М. М. Ямалеевb a Ин-т сист. информ. им. А. П. Ершова СО РАН, пр. Ак. Лаврентьева, 6,
г. Новосибирск, 630090, РОССИЯ
b Казанский (Приволжский) федерал. ун-т, ул. Кремлёвская, 18, г. Казань, 420008, РОССИЯ
Аннотация:
Исследуется задача характеризации собственных уровней тонкой иерархии (с точностью до тьюринговой эквивалентности). Известно, что тонкая иерархия исчерпывает арифметические множества и содержит в качестве малого фрагмента конечные уровни иерархий Ершова (релятивизованных относительно $\varnothing^n$, $n<\omega$), собственность которых известна. Основной результат состоит в нахождении наименьшего нового (т.е. отличного от уровней релятивизиванных иерархий Ершова) собственного уровня. Также показывается, что не все новые уровни будут собственными.
Ключевые слова:
иерархия Ершова, тонкая иерархия, аримфметическая иерархия, тьюринговы степени.
Поступило: 12.12.2016 Окончательный вариант: 20.10.2017
Образец цитирования:
В. Л. Селиванов, М. М. Ямалеев, “О тьюринговых степенях в утончениях арифметической иерархии”, Алгебра и логика, 57:3 (2018), 338–361; Algebra and Logic, 57:3 (2018), 222–236
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al853 https://www.mathnet.ru/rus/al/v57/i3/p338
|
Статистика просмотров: |
Страница аннотации: | 276 | PDF полного текста: | 35 | Список литературы: | 29 | Первая страница: | 10 |
|