Как превзойти алгоритм

Как превзойти алгоритм

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