Доказательство Тьюринга
-
Доказательство неразрешимости проблемы Entscheidungsproblem
- Тьюринг доказывает, что проблема Entscheidungsproblem (проблема определения, является ли формула доказуемой) неразрешима.
- Он использует машину Тьюринга для демонстрации невозможности создания универсального алгоритма для решения этой проблемы.
-
Машина Тьюринга и проблема Entscheidungsproblem
- Машина Тьюринга представляет собой абстрактную вычислительную машину, которая может выполнять конечные последовательности инструкций.
- Проблема Entscheidungsproblem заключается в определении, является ли формула доказуемой в формальной системе.
-
Доказательство Тьюринга
- Тьюринг использует машину Тьюринга для создания машины M, которая выводит последовательность «0-bar» (0) на ленте.
- Машина M может либо печатать «0-bar» бесконечно, либо никогда не печатать его.
- Тьюринг объединяет машины M и E в составную машину G, которая тестирует машины M и определяет, выводят ли они 0.
- Если G обнаруживает, что M выводит 0, это означает, что M не выводит 0 бесконечно, и наоборот.
-
Третье доказательство Тьюринга
- Тьюринг доказывает, что не существует общего процесса для определения, является ли формула U функционального исчисления K доказуемой.
- Он демонстрирует существование формулы Un(M), которая утверждает, что «в некоторой полной конфигурации M на ленте появляется 0».
- Он использует леммы и доведение до абсурда для доказательства того, что Un(M) недоказуема, что означает неразрешимость проблемы Entscheidungsproblem.
- Пересказана только часть статьи. Для продолжения перейдите к чтению оригинала.
Полный текст статьи: