Машина, которая всегда останавливается

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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