Прыжок Тьюринга
-
Определение оператора перехода Тьюринга
- Переход Тьюринга увеличивает степень Тьюринга задачи, делая её неразрешимой с помощью оракула для исходной задачи.
- Оператор перехода связывает задачу с набором машин Тьюринга, останавливающихся при доступе к оракулу для решения исходной задачи.
-
Связь с арифметической иерархией
- Теорема Поста связывает оператор перехода с арифметической иерархией множеств натуральных чисел.
- Скачок Тьюринга по пустому множеству эквивалентен задаче остановки по Тьюрингу.
-
Индуктивное определение и трансфинитные ординалы
- Скачок Тьюринга определяется индуктивно, начиная с первого элемента и заканчивая трансфинитными ординалами.
- Оператор перехода может быть преобразован в трансфинитные ординалы, связанные с гиперарифметической иерархией.
-
Примеры и свойства оператора перехода
- Скачок Тьюринга 0′ эквивалентен задаче остановки по Тьюрингу.
- Множество чисел Геделя истинных формул вычислимо из X (ω).
- Оператор перехода сохраняет свойства перечислимости, но не вычислимости.
- Если A эквивалентно по Тьюрингу B, то A’ эквивалентно по Тьюрингу B’.
- Обратное утверждение неверно.
-
Рекомендации
- Статья Амбос-Спайс и Фейера обсуждает свойства оператора перехода Тьюринга.