Эта публикация цитируется в
2 статьях
$CEA$-операторы и иерархия Ершова. I
М. М. Арсланов,
И. И. Батыршин,
М. М. Ямалеев Казанский (Приволжский) федерал. ун-т, г. Казань, РОССИЯ
Аннотация:
Рассматривается связь между
$CEA$-иерархией и иерархией Ершова в
$\Delta_2^0$-тьюринговых степенях. Степень
$\mathbf c$ называется
$CEA(\mathbf a)$, если
$\mathbf c$ является вычислимо перечислимой относительно
$\mathbf a$, и
$\mathbf a\leq\mathbf c$. Соар и Стоб [Logic colloquium '81, Proc. Herbrand Symp. (Marseille, 1981), (Stud. Logic Found. Math.,
107), North-Hollad, 1982, 299—324] доказали, что для невычислимой низкой в. п. степени
${\mathbf a}$ существует
$CEA(\mathbf a)$, не являющаяся в. п. Позднее, Арсланов, Лемпп и Шор [Ann. Pure Appl. Logic,
78, Nos. 1–3 (1996), 29—56] сформулировали проблему описания таких пар степеней
${\mathbf a}<{\mathbf e}$, что существует
$CEA({\mathbf a})$ $2$-в. п. степень
${\mathbf d}\leq{\mathbf e}$, не являющаяся в. п. С тех пор более 20 лет оставался открытым вопрос: можно ли
$CEA({\mathbf a})$ степень из работы Соара и Стоба сделать
$2$-в. п.? Здесь даётся отрицательный ответ на этот вопрос, который решается в более сильной формулировке: существует такая невычислимая низкая в. п. степень
${\mathbf a}$, что любая
$CEA(\mathbf a)$ $\omega$-в. п. степень является в. п. Также обсуждаются возможные обобщения полученного результата и различные вопросы, связанные с упомянутой проблемой.
Ключевые слова:
$CEA$-иерархия, иерархия Ершова, тьюрингова степень.
УДК:
510.535
Поступило: 03.12.2024
Окончательный вариант: 11.04.2025
DOI:
10.33048/alglog.2024.63.302
Полный текст:
PDF файл (209 kB)