Может показаться, что мы пришли к выводу о существовании по крайней мере несколькихнеразрешимых математических вопросов. Однако это совсем не так! Мы не показали, что существует какая-то необычайно громоздкая машина Тьюринга, для которой (в некотором абсолютном смысле) невозможнорешить вопрос об остановке при ее работе с каким-то особенно громоздким числом — в действительности, все как раз наоборот, как мы сможем скоро убедиться. Мы вообще ничего не говорили о неразрешимости какой-то отдельнойзадачи, а только лишь об алгоритмическойнеразрешимости классовзадач. В каждом конкретном случае ответ будет либо «да», либо «нет», поэтому алгоритм для решения частной задачи, конечно, существует, а именно алгоритм, который при применении к этой задаче просто дает ответ «да» или, может быть, «нет»! Трудность в данном случае состоит в том, что мы не знаем, какойименно из имеющихся алгоритмов применять в том или ином случае. Это вопрос об установлении математической истинности отдельного утверждения, но не об общем решении проблемы для целого класса утверждений. Очень важно сознавать, что сами по себе алгоритмы не доказывают математическую истину. Решение о правомерности использования каждого алгоритма должно всегда приходить извне.

К вопросу о том, как установить истинность математических утверждений, мы вернемся позднее, в связи с теоремой Геделя (см. главу 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 ) этот алгоритм не может решить проблему остановки, т. е. мы тем самым превзошли его. Возможно, мысль о том, что мы «умнее» каких-то алгоритмов, принесет нам некоторое удовлетворение!

На самом деле, упомянутая процедура настолько хорошо определена, что мы могли бы даже найти алгоритмдля нахождения k по заданному H. Поэтому, прежде чем мы «погрязнем» в самодовольстве, мы должны осознать, что этот алгоритм может улучшить H [55] , поскольку он, по сути, «знает», что Т k ( k ) = , - или все-таки нет? В предыдущем изложении было удобно использовать антропоморфный термин «знать» по отношению к алгоритму. Однако не мы ли в конечном счете «знаем», тогда как алгоритм просто следует определенным нами правилам? А может быть мы сами просто следуем правилам, запрограммированным в конструкции нашего мозга и в окружающей нас среде? Эта проблема затрагивает не только алгоритмы, но и то, как мы выносим суждения об истинности и ложности. К этим важнейшим проблемам мы вернемся позднее. Вопрос о математической истине (и ее неалгоритмической природе) будет рассмотрен в главе 4. На данный момент мы, по крайней мере, получили некоторое представление о значениислов «алгоритм» и «вычислимость» и достигли понимания некоторых из относящихся к ним вопросов.