прыжок Тьюринга

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

Оператор называется оператором скачка, потому что он увеличивает степень Тьюринга задачи X. То есть задача X ′ не сводима по Тьюрингу к X. Теорема Поста устанавливает связь между оператором скачка Тьюринга и арифметической иерархией множеств натуральных чисел. [ ^1] Неформально, если задана задача, скачок Тьюринга возвращает набор машин Тьюринга, которые останавливаются при получении доступа к оракулу, решающему эту задачу.

Определение

Скачок Тьюринга X можно рассматривать как оракул к проблеме остановки для машин-оракулов с оракулом для X. ^[1]

Формально, если задано множество X и гёделева нумерация φ _i ^X X -вычислимых функций , то скачок Тьюринга X ′ множества X определяется как

${\displaystyle X'=\{x\mid \varphi _{x}^{X}(x)\ {\mbox{is defined}}\}.}$

n - й скачок Тьюринга X ^{( n )} определяется индуктивно как

${\displaystyle X^{(0)}=X,}$

${\displaystyle X^{(n+1)}=(X^{(n)})'.}$

ω -скачок X ( ^ω) множества X — это эффективное соединение последовательности множеств X ^{( n )} для n ∈ N :

${\displaystyle X^{(\omega )}=\{p_{i}^{k}\mid i\in \mathbb {N} {\text{ and }}k\in X^{(i)}\},}$

где p _i обозначает i-е простое число.

Обозначение 0′ или ∅′ часто используется для обозначения скачка Тьюринга пустого множества. Оно читается как zero-jump или иногда zero-prime .

Аналогично, 0 ^{( n )} является n- м скачком пустого множества. Для конечного n эти множества тесно связаны с арифметической иерархией [ ^2] и, в частности, связаны с теоремой Поста .

Скачок может быть итерирован в трансфинитные ординалы : существуют операторы скачка для множеств натуральных чисел, когда — ординал, имеющий код в коде Клини (независимо от кода, результирующие скачки одинаковы по теореме Спектора), ^[2] в частности, множества 0 ^(α) для α < ω ₁ ^CK , где ω ₁ ^CK — ординал Чёрча–Клини , тесно связаны с гиперарифметической иерархией . ^[1] За пределами ω ₁ ^CK процесс может быть продолжен через счётные ординалы конструктивной вселенной , используя работу Йенсена по теории тонкой структуры L Гёделя . ^{[3] [2]} Эта концепция также была обобщена для распространения на несчетные регулярные кардиналы . ^[4] ${\displaystyle j^{\delta }}$ ${\displaystyle \delta }$ ${\displaystyle {\mathcal {O}}}$

Примеры

• Скачок Тьюринга 0′ пустого множества эквивалентен по Тьюрингу проблеме остановки . ^[5]
• Для каждого n множество 0 ^{( n )} является m-полным на уровне арифметической иерархии ( по теореме Поста ). ${\displaystyle \Sigma _{n}^{0}}$
• Множество чисел Гёделя истинных формул на языке арифметики Пеано с предикатом для X вычислимо из X ^(ω) . ^[6]

Характеристики

• X ′ является X - вычислимо перечислимым , но не X - вычислимым .
• Если A эквивалентно по Тьюрингу B , то A ′ эквивалентно по Тьюрингу B ′ . Обратное утверждение неверно.
• ( Shore and Slaman , 1999) Функция, отображающая X в X ′ , определима в частичном порядке степеней Тьюринга. ^[5]

Многие свойства оператора скачка Тьюринга обсуждаются в статье о степенях Тьюринга .

Ссылки

1. Ambos-Spies, Klaus; Fejer, Peter A. (2014), «Степени неразрешимости», Handbook of the History of Logic , т. 9, Elsevier, стр. 443–494, doi :10.1016/b978-0-444-51624-4.50010-1, ISBN 9780444516244.
2. SG Simpson, Иерархия, основанная на операторе перехода, стр. 269. Симпозиум Клини (Северная Голландия, 1980)
3. Hodes, Harold T. (июнь 1980 г.). «Прыжки через трансфинитное: иерархия главного кода степеней Тьюринга». Журнал символической логики . 45 (2). Ассоциация символической логики : 204–220. doi : 10.2307/2273183. JSTOR  2273183. S2CID  41245500.
4. Любарский, Роберт С. (декабрь 1987 г.). «Несчетные главные коды и иерархия переходов». Журнал символической логики . 52 (4): 952–958. doi :10.2307/2273829. ISSN  0022-4812. JSTOR  2273829. S2CID  46113113.
5. Shore, Richard A.; Slaman, Theodore A. (1999). «Определение скачка Тьюринга». Mathematical Research Letters . 6 (6): 711–722. doi : 10.4310/MRL.1999.v6.n6.a10 .
6. Hodes, Harold T. (июнь 1980 г.). «Прыжок через трансфинитное: иерархия главного кода степеней Тьюринга». Журнал символической логики . 45 (2): 204–220. doi :10.2307/2273183. ISSN  0022-4812. JSTOR  2273183. S2CID  41245500.

• Амбос-Шпис, К. и Фейер, П. Степени неразрешимости. Неопубликовано. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
• Лерман, М. (1983). Степени неразрешимости: локальная и глобальная теория . Берлин; Нью-Йорк: Springer-Verlag . ISBN 3-540-12155-2.
• Любарский, Роберт С. (декабрь 1987 г.). «Несчетные мастер-коды и иерархия переходов». Журнал символической логики . Т. 52, № 4. С. 952–958. JSTOR  2273829.
• Роджерс-младший, Х. (1987). Теория рекурсивных функций и эффективная вычислимость . MIT Press , Кембридж, Массачусетс, США. ISBN 0-07-053522-1.
• Shore, RA; Slaman, TA (1999). «Определение скачка Тьюринга» (PDF) . Mathematical Research Letters . 6 (5–6): 711–722. doi : 10.4310/mrl.1999.v6.n6.a10 . Получено 13 июля 2008 г. .
• Soare, RI (1987). Рекурсивно перечислимые множества и степени: исследование вычислимых функций и вычислимо генерируемых множеств . Springer. ISBN 3-540-15299-7.