1 + 0 = □.
Вопрос о том, останавливается ли конкретная машина Тьюринга или нет, представляет собой совершенно четко определенную математическую задачу (а ранее мы уже видели, что, наоборот, различные важные математические задачи могут быть сведены к вопросу об остановке машины Тьюринга). Таким образом, доказав, что не существует алгоритма для решения вопроса об остановке машины, Тьюринг показал (также как и Черч, который использовал свой собственный и весьма отличающийся подход), что не может быть и общего алгоритма для решения математических задач. Проблема разрешимости Гильберта не имеет решения !
Это не означает, что в каждом отдельномслучае мы не в состоянии выяснить справедливость (или, наоборот, несостоятельность) некоторого конкретного математического утверждения или определить, остановится ли данная машина Тьюринга. С помощью интуиции, искусных технических приемов или же опираясь просто на здравый смысл, мы, вероятно, могли бы получить ответ на такие вопросы в частных случаях. (Так, например, если перечень инструкций некоторой машины Тьюринга не включает ни однойкоманды STOPили же, наоборот, состоит толькоиз таких команд, то одного здравого смысла достаточно для решения вопроса о ее остановке!) Но не существует ни одного алгоритма, который позволял бы решать любуюматематическую задачу или давал ответ на вопрос об остановке любоймашины Тьюринга при любых вводимых в нее числах.
Может показаться, что мы пришли к выводу о существовании по крайней мере несколькихнеразрешимых математических вопросов. Однако это совсем не так! Мы не показали, что существует какая-то необычайно громоздкая машина Тьюринга, для которой (в некотором абсолютном смысле) невозможнорешить вопрос об остановке при ее работе с каким-то особенно громоздким числом — в действительности, все как раз наоборот, как мы сможем скоро убедиться. Мы вообще ничего не говорили о неразрешимости какой-то отдельнойзадачи, а только лишь об алгоритмическойнеразрешимости классовзадач. В каждом конкретном случае ответ будет либо «да», либо «нет», поэтому алгоритм для решения частной задачи, конечно, существует, а именно алгоритм, который при применении к этой задаче просто дает ответ «да» или, может быть, «нет»! Трудность в данном случае состоит в том, что мы не знаем, какойименно из имеющихся алгоритмов применять в том или ином случае. Это вопрос об установлении математической истинности отдельного утверждения, но не об общем решении проблемы для целого класса утверждений. Очень важно сознавать, что сами по себе алгоритмы не доказывают математическую истину. Решение о правомерности использования каждого алгоритма должно всегда приходить извне.
Как превзойти алгоритм
К вопросу о том, как установить истинность математических утверждений, мы вернемся позднее, в связи с теоремой Геделя (см. главу 4). Пока же я бы хотел обратить ваше внимание на то, что доказательство Тьюринга носит гораздо более конструктивный характер и не столь негативно, как могло показаться из предыдущего изложения. Мы ведь не показали, что есть некая определенная машина Тьюринга, для которой абсолютно невозможно решить, останавливается она или нет. Более того, если внимательно проследить за доказательством, то выяснится, что для кажущихся «чрезвычайно сложными» машин сама процедура Тьюринга, использованная для их построения, неявным образом дает ответ! Посмотрим, как это происходит. Допустим, у нас есть алгоритм, который иногдапозволяет определить, что машина Тьюринга не остановится. Вышеописанная процедура Тьюринга позволяет явнопроследить за вычислениями машины Тьюринга в случае, когда этот конкретный алгоритм не дает ответа на вопрос об остановке вычислительного процесса. Однако тем самым эта процедура дает намв этом случае возможность узнать ответ! Конкретная машина Тьюринга, за работой которой мы следим, и вправду никогда не остановится.
Чтобы подробно разобраться в этом вопросе, предположим, что у нас есть некий алгоритм, который иногда позволяет решить проблему остановки. Как и ранее, мы обозначим этот алгоритм (машину Тьюринга) через H, но теперь мы допускаем, что этот алгоритм не всегда может точно определить, что машина Тьюринга не остановится:
так что Н( n ; m ) = □возможно в случае, когда T n ( m ) = □. Существует немало алгоритмов типа Н( n ; m ). (Например, Н( n ; m ) мог бы просто давать на выходе 1, как только машина T n ( m ) останавливается, хотя такойалгоритм едва ли представляет большой практический интерес!)
Мы можем повторить процедуру Тьюринга, следуя уже пройденным путем, с той только разницей, что теперь некоторые из « □» останутся не замененными на нули. Как и ранее, применив диагональный процесс, получим
1 + T n ( n ) х H( n ; n )
в качестве n -го элемента диагонали. (Мы будем иметь □каждый раз, когда H( n ; n ) = □.
Отметим, что □x □= □, 1 + □= □.) Это безупречно алгоритмизованное вычисление, поэтому оно может быть произведено некоторой машиной Тьюринга, скажем k -й, и тогда мы получим
1 + T n ( n ) х H( n ; n ) = Т k ( n ).
Для k -го диагонального элемента (т. е. n = k ) мы имеем
1 + T k ( k ) x H( k ; k ) = T k ( k ).
Если вычисления Т k ( k ) останавливаются, то мы приходим к противоречию (в этом случае Н( k ; k ) должно равняться единице, но тогда возникнет невыполнимое равенство: 1+ Т k ( k ) = Т k ( k ) ). Значит, Т k ( k ) не может остановиться, т. е.
Т k ( k ) = □.
Но алгоритм не может этого «знать», потому что, если бы он давал Н( k ; k ) = 0, мы снова пришли бы к противоречию (мы получили бы тогда неверное соотношение 1+0= □).
Таким образом, если мы можем отыскать k , то мы знаем, как построить вычислительную процедуру, для которой алгоритм не дает решения проблемы остановки, но нам ответ известен! А как нам найти k ? Это непростая задача. Необходимо тщательно изучить конструкцию H( n ; m ) и T n ( m ) и понять, как в точности действует 1 + Т n ( n ) х Н( n ; n ) в качестве машины Тьюринга. Затем надо определить номер этой машины, который и есть k . Конечно, это выполнить трудно, но вполне возможно [54]. Из-за этих трудностей вычисление Т k ( k ) нас бы вовсе не интересовало, не будь она специально предназначена для доказательства неэффективности алгоритма H! Важно то, что мы получили строго определенную процедуру, которая для любого наперед заданного алгоритма Hпозволяет найти такое k , что для Т k ( k ) этот алгоритм не может решить проблему остановки, т. е. мы тем самым превзошли его. Возможно, мысль о том, что мы «умнее» каких-то алгоритмов, принесет нам некоторое удовлетворение!
54
Фактически, самую трудную часть мы уже выполнили, когда построили универсальную машину Тьюринга
U, поскольку она позволяет нам записывать