Выпуск:
Выпуски архив. Вестник ТюмГУ. Физико-математические науки. Информатика (№7, 2013)Об авторе:
Дегтев Александр Николаевич, профессор кафедры алгебры и математической логики Института математики, естественных наук и информационных технологий Тюменского государственного университета, доктор физико-математических наукАннотация:
Построено полурекурсивное рекурсивно перечислимое множество, чья тьюрингова степень находится между 0 и 1, с использованием того факта, что для рекурсивно перечислимых множеств.Ключевые слова:
Список литературы:
1. Post, E.L. Recursively enumerable sets of positive integers and their decision problem// Bull. Amer. Math. Soc. 1944, V.50, N 5, Pp. 284–318.
2. Мучник А.А. Неразрешимость проблемы сводимости теории алгоритмов //ДАН СССР, 1956, Т.108, С. 194–197.
3. Friedberg, R.M. Two recursively enumerable sets of incomparable degrees of insolvability// Proc. Natl. Acad. Sci. USA. 1957, V.43, Pp. 236–238.
4. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость, М.: Мир, 1972.
5. Jockusch C.J. Semirecursive sets and positive reducibility //Trans. Amer. Math. Soc. 1968,
V. 131, N2, Pp. 420–436.
