RUS  ENG
Полная версия
ЖУРНАЛЫ // Ученые записки Казанского университета. Серия Физико-математические науки // Архив

Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 2012, том 154, книга 2, страницы 152–158 (Mi uzku1127)

Relative enumerability and the $d$-c. e. degrees

[Относительная перечислимость и $d$-вычислимо перечислимые степени]

M. M. Arslanov

Department of Algebra and Mathematical Logic, Kazan Federal University, Kazan, Russia

Аннотация: В работе изучается связь между относительной перечислимостью и $d$-вычислимо перечислимыми степенями. Доказано, что тьюринговая степень проблемы остановки машины Тьюринга разложима на такие две вычислимо перечислимые степени, что верхний конус каждой из них состоит только из тех $d$-вычислимо перечислимых степеней, которые перечислимы относительно второй степени.

Ключевые слова: тьюринговые степени, вычислимо перечислимые степени, относительная перечислимость, разложение, определимость.

УДК: 510.532

Поступила в редакцию: 15.12.2010

Язык публикации: английский



© МИАН, 2024