Машина, которая всегда останавливается - Machine that always halts

В теория вычислимости, а машина, которая всегда останавливается, также называемый решающий^[1] или общая машина Тьюринга,^[2] это Машина Тьюринга что в конечном итоге останавливается при каждом вводе.

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

Функции, вычисляемые с помощью тотальных машин Тьюринга

Основная статья: Вычислимая функция

На практике многие интересующие функции вычисляются машинами, которые всегда останавливаются. Машина, которая использует только ограниченный объем памяти для любого конкретного ввода, может быть принудительно остановлена ​​для каждого ввода, ограничив ее управление потоком возможности, так что никакой ввод никогда не заставит машину войти в бесконечный цикл. В качестве тривиального примера, машина, реализующая финитный Древо решений всегда будет останавливаться.

Однако не требуется, чтобы машина была полностью лишена возможности зацикливания, чтобы гарантировать остановку. Если мы ограничим циклы предсказуемо конечным размером (например, цикл FOR в БАЗОВЫЙ ), мы можем выразить все примитивные рекурсивные функции (Мейер и Ричи, 1967). Пример такой машины предоставлен язык программирования игрушек PL- {GOTO} Брейнерда и Ландвебера (1974).

Мы можем дополнительно определить язык программирования, в котором мы можем гарантировать, что даже более сложные функции всегда останутся. Например, Функция Аккермана, который не является примитивно рекурсивным, тем не менее является полностью вычислимой функцией, вычисляемой переписывание терминов система с заказ на сокращение о его аргументах (Ohlebusch, 2002, стр. 67).

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

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

Обычная машина Тьюринга вычислит частичную функцию. Можно задать два вопроса о связи между частичными машинами Тьюринга и полными машинами Тьюринга:

1. Можно ли расширить каждую частичную функцию, вычисляемую частичной машиной Тьюринга (то есть расширить ее область определения), чтобы она стала полностью вычислимой функцией?
2. Можно ли изменить определение машины Тьюринга так, чтобы можно было найти определенный класс полных машин Тьюринга, вычисляющих все полные вычислимые функции?

Ответ на каждый из этих вопросов - нет.

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

Теорема. Есть вычислимые по Тьюрингу частичные функции которые не имеют расширения до полной вычислимой функции Тьюринга. В частности, частичная функция ж определено так, что ж(п) = м тогда и только тогда, когда машина Тьюринга с индексом п останавливается при вводе 0 с выходом м не имеет расширения до полной вычислимой функции.

Действительно, если грамм были полностью вычислимой функцией, расширяющей ж тогда грамм было бы вычислимо какой-нибудь машиной Тьюринга; исправить е как индекс такой машины. Постройте машину Тьюринга M, с помощью Теорема Клини о рекурсии, который на входе 0 имитирует машину с индексом е работает по индексу п_M за M (таким образом, машина M может создать индекс самого себя; это роль теоремы о рекурсии). Предполагается, что это моделирование в конечном итоге вернет ответ. Определять M так что если грамм(п_M) = м затем возвращаемое значение M является м + 1. Таким образом ж(п_M), истинное возвращаемое значение M на входе 0, не будет равняться грамм(п_M). Следовательно грамм не распространяется ж.

Второй вопрос, по сути, задает вопрос, существует ли другая разумная модель вычислений, которая вычисляет только общие функции и вычисляет все общие вычислимые функции. Неформально, если бы такая модель существовала, то каждый из ее компьютеров можно было бы смоделировать с помощью машины Тьюринга. Таким образом, если эта новая модель вычислений состояла из последовательности ${\displaystyle M_{1},M_{2},\ldots }$ машин, было бы рекурсивно перечислимый последовательность ${\displaystyle T_{1},\ldots T_{2},\ldots }$ машин Тьюринга, которые вычисляют полные функции, и так что каждая итоговая вычислимая функция может быть вычислена одной из машин Т_я. Это невозможно, потому что машина ${\displaystyle T}$ можно построить так, чтобы на входе я машина Т возвращается ${\displaystyle T_{i}(i)+1\,}$. Этот компьютер не может быть эквивалентен любому компьютеру T в списке: предположим, что он был в списке по индексу j. потом ${\displaystyle T_{j}(j)=T_{j}(j)+1\,}$, который не возвращает целочисленный результат. Следовательно, она не может быть полной, но функция по построению должна быть полной (если общие функции рекурсивно перечислимы, то эта функция может быть построена), что является противоречием. Это показывает, что на второй вопрос есть отрицательный ответ.

Набор индексов тотальных машин Тьюринга

В проблема решения о том, является ли машина Тьюринга с индексом е будет останавливаться на каждом входе не разрешимо. Фактически эта проблема находится на уровне ${\displaystyle \Pi _{2}^{0}}$ из арифметическая иерархия. Таким образом, эта проблема строго сложнее, чем Проблема с остановкой, который спрашивает, есть ли у машины с индексом е останавливается при вводе 0. Интуитивно это различие в неразрешимости объясняется тем, что каждый экземпляр проблемы «полной машины» представляет бесконечно много экземпляров проблемы остановки.

Смотрите также: Анализ прекращения.

Доказуемость

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

В звук Система доказательств, каждая доказуемо полная машина Тьюринга действительно является тотальной, но обратное неверно: неформально для каждой достаточно сильной системы доказательств первого порядка (включая арифметику Пеано) существуют машины Тьюринга, которые считаются тотальными, но не может быть доказано как таковое, если только система не является непоследовательной (в этом случае можно доказать что угодно). Доказательство их совокупности либо основывается на некоторых предположениях, либо требует другой системы доказательств.

Таким образом, поскольку можно перечислить все доказательства в системе доказательств, можно построить машину Тьюринга на входе n, которая проходит первые n доказательств и ищет противоречие. Если он его находит, он попадает в бесконечный цикл и никогда не останавливается; в противном случае он останавливается. Если система последовательный, машина Тьюринга будет останавливаться при каждом вводе, но невозможно доказать это в достаточно сильной системе доказательств из-за Теоремы Гёделя о неполноте.

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

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

Смотрите также

• BlooP и FlooP
• Полное функциональное программирование
• Анализ прекращения

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

1. Сипсер, 1996 г.^{[нужна цитата ]}
2. Козен, 1997 г.^{[страница нужна ]}

• Брейнерд, У.С., Ландвебер, Л.Х. (1974), Теория вычислений, Wiley.
• Мейер, А.Р., Ричи, Д.М. (1967), Сложность циклических программ, Proc. Национальных собраний ACM, 465.
• Сипсер, М. (2006), Введение в теорию вычислений, PWS Publishing Co.
• Козен, округ Колумбия (1997), Автоматы и вычислимость, Springer.
• Охлебуш, Э. (2002), Расширенные темы по изменению терминов, Springer.