СОВПАДЕНИЕ Q и 𝑄𝑘 СВОДИМОСТЕЙ НА МНОЖЕСТВАХ ИЗ ИЕРАРХИИ ЕРШОВА

Аннотация: Статья посвящена Q-сводимости и иерархии Ершова, играющих важную роль в теории вычислимых функций. Доказано совпадение Q и 𝑄𝑘 сводимостей на множествах из иерархии Ершова. Это является обобщением теоремы В.Д.Соловьева на более широкий класс множеств.
Ключевые слова: вычислимые множества, вычислимо перечислимые множества, сводимости, иерархия Ершова, Т-степень неразрешимости, вычислимая функция.
Данная работа относится к разделу математической логики − вычислимые функции. Рассмотрен вопрос: как ведут себя Q и 𝑄𝑘- сводимости на множествах из иерархии Ершова. Q-сводимость (или еще ее называют квази-сводимость) была введена С. Тенненбаумом (Роджерс, 1972; Odifreddi, 1989), 𝑄𝑘- сводимость была введена В.Д.Соловьевым (Соловьев, 1974). Эти сводимости наряду с T-сводимостью были применены для решения проблемы Поста (Роджерс, 1972; Odifreddi, 1989; Соловьев, 1974) Проблема Поста заключается в нахождении вычислимо перечислимого множества, тьюрингова степень неразрешимости которой лежит строго между вычислимой тьюринговой степенью и полной вычислимо перечислимой тьюринговой степенью.
Впервые эта проблема была решена А.А.Мучником (Мучник, 1956) и Р.М. Фридбергом (Friedberg, 1957), которые использовали “метод приоритета c конечными нарушениями” для построения необходимого множества. Решение этой проблемы получило продолжение: описать класс S= {A | A – вычислимо перечислимое множество и 0 Результаты по Q и 𝑄𝑘 сводимостям представлены в монографиях Х. Роджерса (Роджерс, 1972), Д. Одифреди (Odifreddi, 1989), Р. Соаре (Соар, 2000), а так же в статьях В.Д. Соловьева (Соловьев, 1974) и  Р.Ш. Оманадзе (Оманадзе, 1975; Omanadze, 2018).

Список литературы

1.        Friedberg R. M. Two resursively enumerable sets of incomparable degrees of unsolvability. // Proc.Natl. Acad. Sci. USA 43, 1957, pp. 236-238.

2.        Odifreddi P. Classical Recursion Theory. The Theory of Functions and Sets of Natural Numbers, 1989.

3.        Omanadze R. Sh. // Logic Journal of 7GPL, volume 26, issue 1, 23 January pp. 191-201, 2018.

4.        Putam H. Trial and error predicates and the solution to a problem of Mostowski // Jour. Symb. Log. 30, 1965, pp. 49-57.

5.        Дегтев А. Н. tt и m-степени. // Алгебра и Логика, 12, N2, 1973, pp. 143-161.

6.        Добрица В. П. О проблеме равенства слов на рекурсивно определенных группах // Третья Всес. Конф. по мат. логике, Тезисы докладов, 1974, 63-65 с.

7.        Ершов Ю. Л. Позитивные эквивалентности // Алгебра и Логика, 10, N6, 1971, 620-650 с.

8.        Ершов Ю. Л. Об одной иерархии множеств I // Алгебра и логика, 1968.

9.        Ершов Ю. Л. Об одной иерархии множеств II // Алгебра и Логика, 1968.

10.     Ершов Ю. Л. Об одной иерархии множеств III // Алгебра и логика, 1970.

11.     Ершов Ю. Л. Ершов Ю. Л. Теория нумераций. Наука. 1977.

12.     Марченков С. С. Об одном классе неполных множеств // Мат. Заметки, 20, 1976, 473-478 с.

13.     Мучник А. А. Неразрешимость проблемы сводимости теории алгоритмов. // ДАН СССР, 1956.194-197 с.

14.     Оманадзе Р. Ш. Об одном усилении Q-сводимости // Сибирский фонд алгебры и логики, 1975. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. Мир. 1972 г.

15.     Соар Р. Вычислимо перечислимые множества и степени. // Казанское математическое сообщество, Казань, 2000.

16.     Соловьев В. Д. Q Q-сводимость и гипергиперпростые множества. // Вероятностные методы и кибернетика, выпуск 11. Издательство КГУ, Казань, 1974.