Файл: Пеноуз Роджер. Тени разума. В поисках науки о сознании.doc

Q8. Незавершающиеся вычисления суть идеализи­рованные математические конструкции, по опре­делению бесконечные. Вряд ли подобные вопросы могут иметь сколько-нибудь непосредственное от­ношение к изучению конечных физических объек­тов — таких, как компьютеры или мозг.

Все верно, рассуждая в идеализированном ключе о машинах Тьюринга, незавершающихся вычислениях и т. п., мы рассматри­вали бесконечные (потенциально) процессы, тогда как в случае людей или компьютеров нам приходится иметь дело с системами конечными. И, разумеется, применяя подобные идеализирован­ные доказательства к реальным и конечным физическим объек­там, следует быть готовыми к тому, что такая операция непре­менно окажется связанной с теми или иными ограничениями и оговорками. Однако, как выясняется, учет конечной природы ре­альных объектов не изменяет сколько-нибудь существенно сути доказательства Гёделя—Тьюринга. Нет ничего странного в том, что мы рассуждаем об идеализированных вычислениях, обосно­вываем те или иные умозаключения и выводим, математически, их теоретические ограничения. Можно, к примеру, обсуждать в аб­солютно конечных терминах вопрос о том, существует ли нечет­ное число, являющееся суммой двух четных чисел, или существу­ет ли натуральное число, не являющееся суммой четырех квад­ратов (как в приведенных выше задачах (С) и (В)), нисколько не смущаясь тем, что при рассмотрении этих вопросов мы неявно учитываем бесконечное множество всех натуральных чисел. Мы имеем полное право рассуждать о незавершающихся вычисле­ниях или машинах Тьюринга вообще, как о математических структурах, пусть и не в силах создать на практике бесконеч­но работающую машину Тьюринга. (Отметим, в частности, что действие машины Тьюринга, занятой поисками нечетного числа, являющегося суммой двух четных чисел, строго говоря, практи­чески реализовать невозможно, так как ее детали износятся го­раздо раньше, чем минет вечность.) Описание любого единичного вычисления (или действия машины Тьюринга) — задача вполне конечная, а вопрос о том, завершится ли в конечном итоге это вычисление, можно полагать вполне определенным. Сначала мы доводим до логического завершения теоретические рассуждения, связанные с теми или иными идеализированными вычислениями, и лишь затем пытаемся разглядеть, каким образом наши рассу­ждения применимы к конечным физическим системам — таким, как реально существующие компьютеры или люди.

Ограничения конечного характера могут быть обусловлены либо тем, что (i) описание конкретного рассматриваемого вы­числения оказывается слишком громоздким (т. е. число п в С_п или пара чисел q, n в C_q (n) оказываются слишком велики для того, чтобы их мог описать человек или реально существующий компьютер), либо тем, что (п) при внешней простоте описания вычисление, тем не менее, требует для своего выполнения чрез­мерно много времени, в результате чего может показаться, что оно не завершается вовсе, хотя теоретически данное вычисле­ние должно в конечном счете завершиться. На деле же, как мы вскоре убедимся, выясняется, что из этих двух условий сколько-нибудь существенное влияние на наши рассуждения оказыва­ет только (i), да и оно не так уж и велико. Незначительность фактора (ii), быть может, покажется вам удивительной. Суще­ствует множество относительно простых вычислений, которые в конечном счете завершаются, однако точки их завершения путем прямого вычисления не способен достичь ни один потенциально возможный компьютер. Рассмотрим, например, следующую задачу: «распечатать последовательность из 2^2^65536 единиц, после чего остановиться». (В §3.26 будут предложены еще несколько подобных примеров, гораздо более интересных с математической точки зрения.) Вопрос о завершаемости того или иного вычис­ления не следует решать путем прямого вычисления: этот метод зачастую оказывается крайне неэффективным.

Для того чтобы выяснить, каким образом ограничения (i) или (ii) могут повлиять на наши гёделевские рассуждения, пройдемся еще раз по соответствующим частям доказательства. В соответ­ствии с ограничением (i), вместо бесконечного ряда вычислений, мы располагаем рядом конечным:

, ,,,,…,

где предполагается, что число Q задает наиболее громоздкое вы­числение, какое способен выполнить наш компьютер или чело­век. В случае с человеком вышеприведенное утверждение можно счесть несколько туманным. Впрочем, в настоящий момент нас не особенно заботит точное определение числа Q. (Вопрос о туман­ности утверждений, касающихся человеческих способностей, бу­дет рассмотрен ниже, в комментарии к возражению Q13 в § 2.10.) Кроме того, можно предположить, что, попытавшись применить упомянутые вычисления к какому-то конкретному натуральному числу п, мы обнаружим, что значение п ограничено некоторой фиксированной величиной N, поскольку наш компьютер (или че­ловек) оказывается не способен работать с числами, превыша­ющими N. (Строго говоря, следует учесть и возможность того, что число N не является фиксированным, но зависит от того или иного конкретного вычисления C_q, т. е. N может зависеть от q. Однако этот факт не влияет на наши рассуждения сколько-нибудь существенным образом.)

Как и ранее, мы рассматриваем некий обоснованный ал­горитм A (q, n), завершение выполнения которого равносиль­но доказательству того, что вычисление C_q (n) не завершается. Несмотря на то, что, в соответствии с ограничением (i), рассмот­рению подлежат только значения q, не превышающие Q, и только те значения п, не превышающие N, мы, говоря об «обоснован­ности», в действительности имеем в виду, что алгоритм А должен быть обоснованным для всех значений q и п, независимо от их величины. (Таким образом, можно видеть, что правила, реализуе­мые в алгоритме А, являются точными математическими пра­вилами, в отличие от правил приближенных, работающих только в силу того или иного практического ограничения, налагаемого на «реально осуществимые» вычисления.) Более того, утверждая, что «вычисление C_q (n) не завершается», мы имеем в виду, что это вычисление действительно не завершается, а не то, что это вычисление просто-напросто оказывается слишком громоздким для того, чтобы его мог выполнить наш компьютер или человек, как предусматривает ограничение (ii).

Вспомним, что утверждение (Н) гласит:

Если завершается вычисление А(а,п), то вычисление C_q (n) не завершается.

Принимая во внимание ограничение (ii), можно было бы предпо­ложить, что алгоритм А оказывается не слишком эффективен при установлении факта незавершаемости очередного вычисления, поскольку сам он состоит из большего количества шагов, чем способен выполнить компьютер или человек. Однако, как выяс­няется, для нашего доказательства этот факт не имеет никакого значения. Мы намерены отыскать некое вычисление A (k, k), ко­торое не завершается вообще. Для нас абсолютно неважно, что в некоторых других случаях, когда вычисление А действительно завершается, мы не можем об этом узнать, так как не в состоянии дождаться этого самого завершения.

Далее, как и в равенстве (J), мы вводим натуральное чис­ло k, при котором вычисление А (п, п) совпадает с вычислени­ем Ck (n) для всех n:

А(n,n) = C_k(n).

Следует, впрочем, рассмотреть еще предусматриваемую ограни­чением (i) возможность того, что упомянутое число k окажется больше Q. В случае какого-нибудь невообразимо сложного вы­числения А такая ситуация вполне возможна, однако только при условии, что это А уже начинает приближаться к верхней границе допустимой сложности (в смысле количества двоичных знаков в его описании в формате машины Тьюринга), с которой может работать наш компьютер или человек. Это обусловлено тем, что вычисление, получающее значение k из описания вычисления А (например, в формате машины Тьюринга), — вещь достаточно простая и может быть задана в явном виде (как уже было пока­зано в комментарии к Q6).

Вообще говоря, для того чтобы поставить в тупик алгоритм А, нам необходимо лишь вычисление Ck (k) — подставляя в (Н) равенство n = k, получаем утверждение (L):

Если завершается вычисление A(k, k), то вычисление Ck(k) не завершается.

Поскольку A (k, k) совпадает с Ck (k), наше доказательство по­казывает, что, хотя данное конкретное вычисление Ck (k) никогда не завершается, посредством алгоритма А мы этот факт устано­вить не в состоянии, даже если бы упомянутый алгоритм мог вы­полняться гораздо дольше любого предела, налагаемого на него в соответствии с ограничением (ii). Вычисление Ck (k) задается только введенным ранее числом k, и, при условии, что k не пре­вышает ни Q, ни N, это вычисление и в самом деле в состоянии выполнить наш компьютер или человек — в смысле, в состоянии начать. Довести его до завершения невозможно в любом случае, поскольку это вычисление просто-напросто не завершается!

А может ли число k оказаться больше Q или N? Такое воз­можно лишь в том случае, когда для описания А требуется так много знаков, что даже совсем небольшое увеличение их коли­чества выводит задачу за пределы возможностей нашего ком­пьютера или человека. При этом, поскольку мы знаем об об­основанности алгоритма А, мы знаем и о том, что рассматри­ваемое вычисление C_k(k) не завершается, даже если реальное выполнение этого вычисления представляет для нас проблему. Соображение (i), однако, предполагает и возможность того, что вычисление А окажется столь колоссально сложным, что одно лишь его описание вплотную приблизится к доступному вообра­жению человека пределу сложности, а сравнительно малое уве­личение количества составляющих его знаков даст в результате вычисление, превосходящее всякое человеческое понимание. Что бы мы о подобной возможности ни думали, я все же считаю, что любой столь впечатляющий набор реализуемых в нашем гипо­тетическом алгоритме А вычислительных правил окажется, вне всякого сомнения, настолько сложным, что мы не в состоянии будем наверняка знать, является ли он обоснованным, даже если нам будут точно известны все эти правила по отдельности. Таким образом, наше прежнее заключение остается в силе: при установлении математических истин мы не применяем познава­емо обоснованные наборы алгоритмических правил.

Не помешает несколько более подробно остановиться на сравнительно незначительном увеличении сложности, сопрово­ждающем переход от А к C_k(k). Помимо прочего, это существен­но поможет нам в нашем дальнейшем исследовании (в §§3.19 и 3.20). В Приложении А (с. 191) предложено явное описание вычисления Ck(k) в виде предписаний для машины Тьюринга, рассмотренных в НРК (глава 2). Согласно этим предписаниям, под обозначением Т_т понимается «m-я машина Тьюринга». Для большего удобства и упрощения рассуждений здесь мы также будем пользоваться этим обозначением вместо «С_m», в част­ности, для определения степени, сложности вычислительной процедуры или отдельного вычисления. В соответствии с выше­сказанным, определим степень сложности  машины Тьюрин­га Т_т как количество знаков в двоичном представлении числа т (см. НРК, с. 39); при этом степень сложности некоторого вы­числения Т_т (п) определяется как большее из двух чисел  и v, где v — количество двоичных знаков в представлении числа п. Рассмотрим далее приведенное в Приложении А явное предпи­сание для составления вычисления Ck(k) на основании алгорит­ма А, заданного в упомянутых спецификациях машины Тьюринга. Полагая степень сложности А равной а, находим, что степень сложности явного вычисления Ck (k) не превышает числа а + 210 log₂ (а + 336) — а это число, в свою очередь, оказывается лишь очень ненамного больше собственно а, да и то только тогда, когда число а очень велико.

В вышеприведенных общих рассуждениях имеется один по­тенциально спорный момент. В самом деле, какой смысл рас­сматривать вычисления, слишком сложные даже для того, чтобы просто их записать, или те, что, будучи записанными, возмож­но, потребуют на свое действительное выполнение промежуток времени, гораздо больший предполагаемого возраста нашей Все­ленной, даже при условии, что каждый шаг такого вычисления будет производиться за самую малую долю секунды, какая еще допускает протекание каких бы то ни было физических процес­сов? Упомянутое выше вычисление — то, результатом которого является последовательность из  единиц и которое завершается лишь после выполнения этой задачи, — представля­ет собой как раз такой пример, при этом позицию математика, позволяющего себе утверждать, что данное вычисление является незавершающимся, можно охарактеризовать как крайне нетра­диционную. Однако в математике существуют и некоторые другие точки зрения, пусть и не до такой степени нетрадиционные, — но все же решительно презирающие всяческие условности, — согласно которым известная доля здорового скептицизма в отно­шении вопроса об абсолютной математической истинности иде­ализированных математических утверждений отнюдь не поме­шает. На некоторые из них, безусловно, стоит хотя бы мельком