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

• Определение оператора перехода Тьюринга

  • Переход Тьюринга увеличивает степень Тьюринга задачи, делая её неразрешимой с помощью оракула для исходной задачи. 
  • Оператор перехода связывает задачу с набором машин Тьюринга, останавливающихся при доступе к оракулу для решения исходной задачи. 

• Связь с арифметической иерархией

  • Теорема Поста связывает оператор перехода с арифметической иерархией множеств натуральных чисел. 
  • Скачок Тьюринга по пустому множеству эквивалентен задаче остановки по Тьюрингу. 

• Индуктивное определение и трансфинитные ординалы

  • Скачок Тьюринга определяется индуктивно, начиная с первого элемента и заканчивая трансфинитными ординалами. 
  • Оператор перехода может быть преобразован в трансфинитные ординалы, связанные с гиперарифметической иерархией. 

• Примеры и свойства оператора перехода

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

• Рекомендации

  • Статья Амбос-Спайс и Фейера обсуждает свойства оператора перехода Тьюринга.