Решающий модуль (машина Тьюринга)

• Определение и свойства решающих модулей

  • Решающий модуль — это машина Тьюринга, которая останавливается на каждом входе. 
  • Решающий модуль также известен как полная машина Тьюринга. 
  • Решающие модули могут определить, является ли строка членом рекурсивного языка. 

• Неразрешимость определения решающего модуля

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

• Примеры функций, вычисляемых решающими модулями

  • Решающие модули могут вычислять функции, которые всегда останавливаются, даже если они ограничены памятью. 
  • Пример — конечное дерево решений. 
  • Некоторые функции, такие как функция Аккермана, могут быть вычислены с помощью решающих модулей. 

• Связь с частичными машинами Тьюринга

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

• Невозможность создания полной модели вычислений

  • Не существует модели вычислений, которая вычисляет только полные функции и вычисляет все полные функции. 
  • Построение машины Тьюринга, которая имитирует другие машины Тьюринга, приводит к противоречиям. 

• Проблема принятия решений о полной остановке

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

• Доказуемость полной остановки машины Тьюринга

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

• Примеры машин Тьюринга, которые не могут быть доказаны

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