|
Ученые записки Казанского университета. Серия Физико-математические науки, 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$-вычислимо перечислимых степеней, которые перечислимы относительно второй степени.
Ключевые слова:
тьюринговые степени, вычислимо перечислимые степени, относительная перечислимость, разложение, определимость.
Поступила в редакцию: 15.12.2010
Образец цитирования:
M. M. Arslanov, “Relative enumerability and the $d$-c. e. degrees”, Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 154, no. 2, Изд-во Казанского ун-та, Казань, 2012, 152–158
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/uzku1127 https://www.mathnet.ru/rus/uzku/v154/i2/p152
|
Статистика просмотров: |
Страница аннотации: | 201 | PDF полного текста: | 57 | Список литературы: | 38 |
|