В теории вычислимости решатель — это машина Тьюринга , которая останавливается при каждом вводе. [1] Решатель также называется полной машиной Тьюринга [2], поскольку он представляет собой полную функцию .
Поскольку она всегда останавливается, такая машина способна решить, является ли данная строка членом формального языка . Класс языков, которые могут быть определены такими машинами, — это множество рекурсивных языков .
Если задана произвольная машина Тьюринга, то определение того, является ли она решателем, является неразрешимой проблемой . Это вариант проблемы остановки , которая спрашивает, останавливается ли машина Тьюринга на определенном входе.
На практике многие функции, представляющие интерес, вычисляются машинами, которые всегда останавливаются. Машину, которая использует только конечную память для любого конкретного ввода, можно заставить останавливаться для каждого ввода, ограничив ее возможности управления потоком , так что никакой ввод никогда не заставит машину войти в бесконечный цикл . В качестве тривиального примера, машина, реализующая конечное дерево решений, всегда остановится.
Однако не требуется, чтобы машина была полностью свободна от циклических возможностей, чтобы гарантировать остановку. Если мы ограничим циклы предсказуемо конечным размером (как цикл FOR в BASIC ), мы сможем выразить все примитивные рекурсивные функции (Мейер и Ритчи, 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 может производить индекс самой себя; в этом заключается роль теоремы о рекурсии). По предположению, эта симуляция в конечном итоге вернет ответ. Определим M [ проясним ] так, что если g ( n M ) = m , то возвращаемое значение M равно . Таким образом, f ( n M ), истинное возвращаемое значение M на входе0 , не будет равен g ( n M ). Следовательно, g не расширяет f .
Второй вопрос, по сути, спрашивает, существует ли другая разумная модель вычислений, которая вычисляет только полные функции и вычисляет все полные вычислимые функции. Неформально, если бы такая модель существовала, то каждый из ее компьютеров мог бы быть смоделирован машиной Тьюринга. Таким образом, если бы эта новая модель вычислений состояла из последовательности машин, то была бы рекурсивно перечислимая последовательность машин Тьюринга, которые вычисляют полные функции, и так, что каждая полная вычислимая функция была бы вычислима одной из машин T i . Это невозможно, потому что машина T могла бы быть построена так, что на входе i машина T возвращала бы . Эта машина не может быть эквивалентна ни одной машине T в списке: предположим, что она была бы в списке под индексом j . Тогда , что не возвращает целочисленный результат. Следовательно, она не может быть полной, но функция по построению должна быть полной (если полные функции рекурсивно перечислимы, то эта функция может быть построена), что является противоречием. Это показывает, что второй вопрос имеет отрицательный ответ.
Проблема принятия решения о том, остановится ли машина Тьюринга с индексом e на каждом входе, неразрешима. Фактически, эта проблема находится на уровне арифметической иерархии . Таким образом, эта проблема строго сложнее, чем проблема остановки , которая спрашивает, остановится ли машина с индексом e на входе 0. Интуитивно эта разница в неразрешимости заключается в том, что каждый экземпляр проблемы «полной машины» представляет собой бесконечно много экземпляров проблемы остановки.
Может быть интересно не только то, является ли машина Тьюринга тотальной, но и то, можно ли это доказать в определенной логической системе, например, в арифметике Пеано первого порядка .
В системе звукового доказательства каждая доказуемо полная машина Тьюринга действительно является полной, но обратное неверно: неформально, для каждой системы доказательства первого порядка, которая достаточно сильна (включая арифметику Пеано), существуют машины Тьюринга, которые считаются полными, но не могут быть доказаны как таковые, если только система не является противоречивой (в этом случае можно доказать что угодно). Доказательство их тотальности либо основывается на некоторых предположениях, либо требует другой системы доказательства.
Таким образом, поскольку можно перечислить все доказательства в системе доказательств, можно построить машину Тьюринга на входе n, которая проходит по первым n доказательствам и ищет противоречие. Если она находит его, она попадает в бесконечный цикл и никогда не останавливается; в противном случае она останавливается. Если система непротиворечива , машина Тьюринга остановится на каждом входе, но доказать это в достаточно сильной системе доказательств невозможно из-за теорем Гёделя о неполноте .
Можно также создать машину Тьюринга, которая остановится тогда и только тогда, когда система доказательств противоречива и, таким образом, не является полной для последовательной системы, но не может быть доказана следующим образом: это машина Тьюринга, которая независимо от входных данных перебирает все доказательства и останавливается при противоречии.
Машина Тьюринга, которая проходит по последовательностям Гудстейна и останавливается на нуле, является тотальной, но это не может быть доказано в арифметике Пеано.
