Введение
Машина Тьюринга, которая останавливается для любого ввода.
В теории вычислимости, децидер – это машина Тьюринга, которая останавливается на любом вводе. Децидер также называют полной машиной Тьюринга, поскольку он представляет собой полную функцию. Поскольку она всегда останавливается, такая машина способна определить, является ли заданная строка элементом формального языка. Класс языков, которые могут быть решены такими машинами, – это множество рекурсивных языков. Определение того, является ли произвольная машина Тьюринга децидером, является неразрешимой задачей. Это вариант проблемы останова, которая спрашивает, останавливается ли машина Тьюринга на конкретном вводе.
Функции, вычисляемые с помощью машин Тьюринга
На практике многие интересующие нас функции могут быть вычислены машинами, которые всегда завершают работу. Машину, использующую только конечный объем памяти для любого конкретного ввода, можно заставить завершиться для любого ввода, ограничив ее возможности управления потоком выполнения так, чтобы ни один ввод не приводил к бесконечному циклу. В качестве тривиального примера, машина, реализующая конечное дерево решений, всегда завершит работу. Однако для гарантии завершения работы не требуется, чтобы машина полностью лишалась возможности циклических вычислений. Если мы ограничим циклы предсказуемо конечным размером (например, как цикл FOR в BASIC), мы сможем выразить все примитивно рекурсивные функции (Meyer и Ritchie, 1967). Примером такой машины является игрушечный язык программирования PL {GOTO} Брайнерда и Ландвебера (1974). Мы можем определить язык программирования, в котором можно гарантировать, что даже более сложные функции всегда завершатся. Например, функция Аккермана, которая не является примитивно рекурсивной, тем не менее является тотально вычислимой функцией, вычисляемой системой переписывания термов с отношением уменьшения по аргументам (Ohlebusch, 2002, с. 67). Несмотря на приведенные примеры языков программирования, гарантирующих завершение программ, не существует языка программирования, который бы точно соответствовал классу тотально рекурсивных функций, то есть функций, которые могут быть вычислены машиной Тьюринга, всегда завершающей работу. Это связано с тем, что существование такого языка привело бы к противоречию с неразрешимостью проблемы определения, завершится ли машина Тьюринга на любом вводе.
Набор индексов всех машин Тьюринга
Проблема определения, остановится ли машина Тьюринга с индексом e на любом входе, неразрешима. Более того, эта проблема находится на уровне арифметической иерархии. Следовательно, она строго сложнее, чем проблема останова, которая спрашивает, остановится ли машина с индексом e на входе 0. Интуитивно, эта разница в неразрешимости объясняется тем, что каждый экземпляр проблемы о "тотальной машине" представляет собой бесконечно много экземпляров проблемы об остановке.
Доказательность
Можно интересоваться не только тем, является ли машина Тьюринга тотальной, но и тем, возможно ли это доказать в определенной логической системе, такой как арифметика Пеано первого порядка. В корректной системе доказательств любая доказуемо тотальная машина Тьюринга действительно тотальна, но обратное неверно: неформально, для каждой достаточно сильной системы доказательств первого порядка (включая арифметику Пеано) существуют машины Тьюринга, которые считаются тотальными, но не могут быть доказаны как таковые, если система не является противоречивой (в этом случае можно доказать всё что угодно). Доказательство их тотальности либо опирается на определенные предположения, либо требует другой системы доказательств. Поскольку все доказательства в системе доказательств можно перечислить, можно построить машину Тьюринга, которая на входе n просматривает первые n доказательств в поисках противоречия. Если противоречие найдено, машина зацикливается и никогда не останавливается; в противном случае, она останавливается. Если система непротиворечива, машина Тьюринга остановится на любом входе, но это нельзя доказать в достаточно сильной системе доказательств из-за теорем о неполноте Гёделя. Также можно создать машину Тьюринга, которая остановится тогда и только тогда, когда система доказательств противоречива, и, следовательно, не будет тотальной для непротиворечивой системы, но это также нельзя доказать. Эта машина Тьюринга, независимо от входных данных, перечисляет все доказательства и останавливается при обнаружении противоречия. Машина Тьюринга, проходящая по последовательности Гудштейна и останавливающаяся на нуле, является тотальной, но её тотальность нельзя доказать в арифметике Пеано.