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

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

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

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

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

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

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

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

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

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

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

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

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

В самом деле, если бы g была полностью вычислимой функцией, расширяющей f, то g была бы вычислима с помощью некоторой машины Тьюринга; зафиксируйте e как индекс такой машины. Постройте машину Тьюринга M , используя теорему о рекурсии Клини , которая при вводе0 имитирует машину с индексом e, работающую с индексом n _M для M (таким образом, машина M может создать собственный индекс; это роль теоремы о рекурсии). Предполагается, что это моделирование в конечном итоге вернет ответ. Определим M так , что если г ( п _М ) = т , то возвращаемое значение М является . Таким образом, f ( n _M ), истинное возвращаемое значение M на входе${\ displaystyle m + 1}$0 , не будет равно g ( n _M ). Следовательно, g не продолжает f .

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

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

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

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

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

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

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

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

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

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

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

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

использованная литература

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