Решатель (машина Тьюринга)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

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

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

[1] Сипсер, 1996. ^{[ нужна страница ]}

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

[1]

[2]