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

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

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

Определение [ править ]

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

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

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

прыжок $n-й$ Тьюринга $X (н)$ определяется индуктивно как

X^{(0)}=X,

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

Скачок $ω$  $X (ой)$ из $X$ является эффективным объединением последовательности множеств $X (н)$ для $n \in N$ :

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

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

Обозначение $0 '$ или $\emptyset '$ часто используется для обозначения скачка Тьюринга пустого множества. Читается как нулевой переход или иногда как нулевой простой .

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

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

Примеры [ править ]

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

Свойства [ править ]

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

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

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б ^с Амбос-Спис, Клаус; Фейер, Питер А. (2014), «Степени неразрешимости», Справочник по истории логики , том. 9, Elsevier, стр. 443–494, doi : 10.1016/b978-0-444-51624-4.50010-1 , ISBN. 9780444516244 .
^ Jump up to: Перейти обратно: ^а ^б ^с С.Г. Симпсон, Иерархия, основанная на операторе перехода , стр.269. Симпозиум Клини (Северная Голландия, 1980 г.)
^ Ходс, Гарольд Т. (июнь 1980 г.). «Прыжок через трансфинитное: иерархия главных кодов степеней Тьюринга» . Журнал символической логики . 45 (2). Ассоциация символической логики : 204–220. дои : 10.2307/2273183 . JSTOR 2273183 . S2CID 41245500 .
^ Любарский, Роберт С. (декабрь 1987 г.). «Бесчисленные мастер-коды и иерархия прыжков». Журнал символической логики . 52 (4): 952–958. дои : 10.2307/2273829 . ISSN 0022-4812 . JSTOR 2273829 . S2CID 46113113 .
^ Jump up to: Перейти обратно: ^а ^б Шор, Ричард А.; Сламан, Теодор А. (1999). «Определение прыжка Тьюринга» . Письма о математических исследованиях . 6 (6): 711–722. дои : 10.4310/MRL.1999.v6.n6.a10 .
^ Ходс, Гарольд Т. (июнь 1980 г.). «Прыжок через трансфинитное: иерархия мастер-кодов степеней Тьюринга» . Журнал символической логики . 45 (2): 204–220. дои : 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 .
Шор, РА; Сламан, Т.А. (1999). «Определение скачка Тьюринга» (PDF) . Письма о математических исследованиях . 6 (5–6): 711–722. дои : 10.4310/mrl.1999.v6.n6.a10 . Проверено 13 июля 2008 г.
Соаре, Род-Айленд (1987). Рекурсивно перечислимые множества и степени: исследование вычислимых функций и вычислимо порожденных множеств . Спрингер. ISBN 3-540-15299-7 .

[:0-1] Jump up to: Перейти обратно: ^а ^б ^с Амбос-Спис, Клаус; Фейер, Питер А. (2014), «Степени неразрешимости», Справочник по истории логики , том. 9, Elsevier, стр. 443–494, doi : 10.1016/b978-0-444-51624-4.50010-1 , ISBN. 9780444516244 .

[Simpson80-2] Jump up to: Перейти обратно: ^а ^б ^с С.Г. Симпсон, Иерархия, основанная на операторе перехода , стр.269. Симпозиум Клини (Северная Голландия, 1980 г.)

[3] Ходс, Гарольд Т. (июнь 1980 г.). «Прыжок через трансфинитное: иерархия главных кодов степеней Тьюринга» . Журнал символической логики . 45 (2). Ассоциация символической логики : 204–220. дои : 10.2307/2273183 . JSTOR 2273183 . S2CID 41245500 .

[4] Любарский, Роберт С. (декабрь 1987 г.). «Бесчисленные мастер-коды и иерархия прыжков». Журнал символической логики . 52 (4): 952–958. дои : 10.2307/2273829 . ISSN 0022-4812 . JSTOR 2273829 . S2CID 46113113 .

[:1-5] Jump up to: Перейти обратно: ^а ^б Шор, Ричард А.; Сламан, Теодор А. (1999). «Определение прыжка Тьюринга» . Письма о математических исследованиях . 6 (6): 711–722. дои : 10.4310/MRL.1999.v6.n6.a10 .

[6] Ходс, Гарольд Т. (июнь 1980 г.). «Прыжок через трансфинитное: иерархия мастер-кодов степеней Тьюринга» . Журнал символической логики . 45 (2): 204–220. дои : 10.2307/2273183 . ISSN 0022-4812 . JSTOR 2273183 . S2CID 41245500 .

[1]

[2]

[3]

[4]

[5]

[6]