ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда - Хофштадтер Даглас Р.

Насколько хорошо можно научить компьютер выскакивать за пределы системы? Я приведу пример, в свое время удививший многих наблюдателей. Не так давно на шахматном чемпионате среди компьютеров у одной из программ (самой слабой) оказалась необычайная особенность — сдаваться задолго до конца партии. Она не была хорошим игроком, зато умела увидеть, когда позиция становилась безнадежной, и сдаться в этот момент, вместо того, чтобы ждать, пока другая программа пройдет через скучную процедуру матования. Хотя та программа проиграла все свои партии, она сделала это с шиком, удивив многих местных знатоков шахмат. Таким образом, если мы определим здесь «систему» как «делать ходы шахматной партии», ясно, что та программа имела сложную, заранее запрограммированную способность выходить из системы. С другой стороны, если вы считаете, что «системой» в данном случае является «все то, что компьютер запрограммирован делать», несомненно, что та программа вовсе не умела выходить из системы.

Изучая формальные системы, очень важно отличать работу внутри системы от наших наблюдений над системой. Наверное, подобно большинству читателей, вы начали работу над головоломкой MU внутри системы; однако в какой-то момент ваше терпение истощилось и вы вышли из системы, пытаясь проанализировать результаты вашей работы и понять, почему вам до сих пор не удалось получить MU. Возможно, вы смогли ответить на этот вопрос; это — пример размышления о системе. Вероятно, в какой-то момент вы вывели MIU; это — пример работы внутри системы. Я не хочу сказать, что эти два метода совершенно несовместимы; напротив, я уверен, что любой человек до определенной степени способен одновременно работать внутри системы и размышлять над тем, что он делает. Более того, в человеческих делах часто почти невозможно точно отделить работу внутри системы от ее анализа; жизнь состоит из такого количества сложных, переплетенных между собой систем, что подобное деление вообще кажется слишком большим упрощением. Однако сейчас для нас важно четко сформулировать простые идеи, чтобы в дальнейшем мы могли опираться на них при анализе более сложных систем. Именно поэтому я рассказываю вам о формальных системах; кстати, нам пора вернуться к обсуждению системы MIU.

Головоломка MU была сформулирована таким образом, чтобы читатель некоторое время работал внутри системы, выводя теоремы. В то же время, ее формулировка не обещала, что, оставаясь внутри системы, он сможет добиться результата. Таким образом, система MIU предполагает некоторое колебание между двумя режимами работы. Эти режимы можно разделить, используя два листа бумаги: на одном из них вы работаете «в качестве машины», заполняя лист теоремами; на другом вы работаете «в качестве мыслящего существа» и можете делать все, что вам подскажет смекалка: использовать русский язык, записывать идеи, работать в обратном порядке, использовать иксы, сжимать несколько шагов в один, менять правила системы, чтобы посмотреть, что из этого выйдет — короче, все, что придет вам в голову. Вы можете заметить, что числа 3 и 2 играют важную роль в системе, так как I сокращаются группами по 3, a U — группами по 2; кроме того, правило II позволяет удвоение букв (кроме M). На втором листе бумаги у вас могут содержаться какие-то размышления по этому поводу. Позже мы еще вернемся к этим двум способам работы с формальными системами; мы будем называть их механический режим (способ M) и интеллектуальный режим (способ I). Каждой букве системы MIU соответствует один из режимов. В дальнейшем я опишу последний режим — ультра-режим (режим U), свойственный дзен-буддистскому подходу к вещам. Подробнее об этом через несколько глав.

Работая над этой головоломкой, вы, вероятно, заметили, что она включает правила двух противоположных типов удлиняющие и укорачивающие. Два правила (I и II) позволяют нам удлинять строчки (естественно, лишь строго определенным образом), два других правила позволяют укорачивать строчки (опять же, следуя строгому закону). Кажется, что порядок применения этих правил можно бесконечно варьировать; таким образом, возникает надежда, что рано или поздно мы придем к искомой строчке MU. Возможно, нам придется создать для этого гигантскую строчку и затем сокращать ее, пока не останутся только два символа; или, того хуже, нам придется попеременно удлинять и сокращать, удлинять и сокращать, и так далее. При этом успех не гарантирован. На самом деле, мы уже заметили, что получить U вообще невозможно, даже если бы мы удлиняли и сокращали строчки до второго пришествия.

Тем не менее, кажется, что с MU ситуация иная, чем с U. Наше заключение о том, что U вывести невозможно, основывалось на очевидном свойстве этой строчки она не начинается с M, как все остальные теоремы. Иметь такой простой способ отличать не-теоремы весьма удобно. Однако кто может поручиться, что подобный способ укажет нам все не-теоремы? Вполне возможно, что существует множество начинающихся с M строчек, которые, тем не менее, невыводимы. Это означало бы, что проверка «по первой букве» указывает нам только на ограниченное количество не-теорем, оставляя «за бортом» все остальные. Однако существует возможность найти некий более сложный метод проверки, точно говорящий нам, какие строчки могут быть выведены с помощью данных правил, а какие — нет. Тут перед нами возникает вопрос: что мы подразумеваем под словом «проверка»? Читателю может быть не совсем понятно, какой смысл задаваться этим вопросом и почему он столь важен в данном контексте. Приведу пример такой «проверки», которая, как кажется, идет вразрез с самим смыслом этого слова.

Представьте себе джинна, в распоряжении которого имеется все время на свете. Джинн тратит это время на вывод теорем системы MIU. Делает он это весьма методично, скажем, следующим образом:

Шаг 1: Приложить все подходящие правила к аксиоме MI. Это дает две новые теоремы: MIU, MII.

Шаг 2: Приложить все подходящие правила к теоремам, полученным в шаге 1. Это дает три новые теоремы: MIIU, MIUIU, MIIII.

Шаг 3: Приложить все подходящие правила к теоремам, полученным в шаге 2. Это дает пять новых теорем: MUIIIIU, MIIUIIU, MIUIUIUIU, МIIIIIIII, MUI.

.

.

.

Следуя этому методу, рано или поздно мы выведем каждую теорему системы, так как правила применяются во всех мыслимых комбинациях. (См. рис. 11) Все удлиняющие и укорачивающие трансформации, упомянутые выше, со временем будут осуществлены.

Рис. 11. Систематически построенное «дерево» всех теорем системы MIU. N-ный уровень внизу содержит теоремы, для вывода которых понадобилось ровно N шагов. Номера в кружках говорят нам, с помощью какого правила была получена данная теорема. Растет ли на этом дереве MU?

Неясно, однако, как долго нам придется ждать появления той или иной строчки, поскольку теоремы расположены согласно длине их вывода. Это не очень-то полезное расположение, в особенности, если вы заинтересованы в какой-то определенной строчке (например, MU) и при этом не знаете не только того, какой длины ее вывод, но даже того, существует ли этот вывод вообще. Теперь давайте взглянем на обещанную «проверку теоремности»:

Ждите, пока данная строчка будет выведена; когда это случится, вы будете знать, что это — теорема. Если же этого не случится никогда, вы можете быть уверены, что данная строчка — не теорема.

Это звучит нелепо, так как здесь имеется в виду, что мы согласны ждать ответа до скончания веков. Таким образом, мы опять подошли к вопросу о том, что может считаться «проверкой». Прежде всего, нам необходима гарантия, что мы получим ответ за ограниченный промежуток времени. Такая проверка теоремности, которая завершается в конечный отрезок времени, называется алгоритмом разрешения для данной формальной системы.