1.9. Невычислительные процессы

Из всех типов вполне определенных процессов, что приходят в голову, большая часть относится, соответственно, к категории феноменов, называемых мною «вычислительными» (имеются в виду, конечно же, «цифровые вычисления»). Возможно, читатель уже начал волноваться, что сторонники позиции так и оста­нутся у нас не при деле. Причем я еще ни словом не упоминал о строго случайных процессах, которые могут быть обуслов­лены, скажем, какими-либо исходными данными, получаемыми от квантовой системы. (О квантовой механике мы немного по­дробнее поговорим во второй части, главы 5 и 6.) Впрочем, для самой системы практически безразлично, подается на ее вход подлинно случайная последовательность данных или же всего лишь псевдослучайная, которую можно целиком и полностью сгенерировать вычислительным путем (см. §3.11). Действитель­но, несмотря на то, что между «случайным» и «псевдослучай­ным», строго говоря, существуют некоторые формальные отли­чия, они, на первый взгляд, не имеют непосредственного отно­шения к проблемам ИИ. Далее, в §3.11, §3.18 и последующих, я приведу некоторые серьезные доводы в пользу того, что «чистая случайность» и в самом деле абсолютно бесполезна для наших целей; если уж возникает такая необходимость, то лучше все же придерживаться псевдослучайности хаотического поведения, а все нормальные типы хаотического поведения, как уже подчер­кивалось выше, относятся к категории «вычислительных».

А что нам известно о роли окружения? По мере развития каждого индивидуума у него или у нее формируется уникаль­ное окружение, отличное от окружения любого другого человека. Возможно, именно это уникальное личное окружение и дает каж­дому из нас ту особенную последовательность входных данных, которая неподвластна вычислению? Хотя лично мне, например, сложно сообразить, на что именно в данном контексте может повлиять «уникальность» нашего окружения. Эти рассуждения напоминают разговор о хаосе, который мы вели выше (см. § 1.7). Для обучения управляемого компьютером робота достаточно од­ной лишь модели некоего правдоподобного окружения (хаоти­ческого), при том, разумеется, условии, что в этой модели не будет ничего заведомо невычислимого. Роботу нет нужды учиться тем или иным навыкам в каком-то конкретном реальном окружении; его, разумеется, вполне устроит типичное окружение, модели­рующее реальность вычислительными методами.

А может быть, численное моделирование пусть даже все­го лишь правдоподобного окружения невозможно в принципе. Быть может, в окружающем физическом мире есть-таки нечто такое, что на самом деле неподвластно численному моделиро­ванию. Возможно, некоторые сторонники уже воз­намерились приписать все не поддающиеся, на первый взгляд, вычислению проявления человеческого поведения невычислимо­сти внешнего окружения. Должен, однако, заметить, что намере­ние это несколько опрометчиво. Ибо, как только мы признаем, что физическое поведение допускает где-то что-то такое, что невозможно моделировать вычислительными методами, мы тем самым тут же лишаемся главного, по всей видимости, основания сомневаться в правдоподобии, в первую очередь, самой точки зрения . Если во внешнем окружении (т.е. вне мозга) имеют место процессы, не поддающиеся численному моделированию, то почему не могут оказаться таковыми и процессы, протекающие внутри мозга? В конце концов, внутренняя физическая органи­зация мозга человека, по всей видимости, гораздо более сложна, чем большая часть (и это еще слабо сказано) его окружения, за исключением, быть может, тех его участков, где это окружение само оказывается под сильным влиянием деятельности других

мозгов. Признание возможности внешней невычислимой физи­ческой активности лишает всякой силы главный аргумент про­тив . (См. также §3.9, §3.10.)

Следует сделать еще одно замечание относительно «не под­дающихся вычислению» процессов, возможность существования которых предполагает позиция . Под этим термином я имею в виду отнюдь не те процессы, которые всего-навсего невычис­лимы практически. Здесь, конечно же, уместно вспомнить и о том, что, хотя моделирование любого правдоподобного окру­жения, или же любое точное воспроизведение всех физических и химических процессов, протекающих в мозге, может быть, в принципе, вычислимым, на такое вычисление, скорее всего, по­надобится столько времени или такой объем памяти, что вряд ли удастся выполнить его на любом реально существующем или даже вообразимом в ближайшем будущем компьютере. Вероят­но, нереально даже написание соответствующей компьютерной программы, если учесть, какое огромное количество различных факторов придется принимать в расчет. Однако сколь бы суще­ственными ни были все эти соображения (а мы еще вернемся к ним в они не имеют никакого отношения к тому, что называю «невычислимостью» я (и чего требует ). Под «невычислимостью» я подразумеваю принципиальную невоз­можность вычисления в том смысле, который мы очень скоро об­судим. Вычисления, которые просто выходят за рамки существу­ющих или вообразимых компьютеров, или имеющихся в нашем распоряжении вычислительных методов, формально все равно остаются «вычислениями».

Читатель имеет полное право спросить: если ничего, что можно счесть «невычислимым», не обнаруживается ни в случай­ности, ни во влиянии окружения, ни в банальном несоответствии уровня сложности феномена нашим техническим возможностям, то что вообще я имею в виду, говоря «чего требует »? В общем случае, это некий вид математически точной активности, невы­числимость которой можно доказать. Насколько нам на данный момент известно, при описании физического поведения в подоб­ной математической активности необходимости не возникает. Тем не менее, логически она возможна. Более того, она представляет собой нечто большее, нежели просто логическую возможность. Согласно приводимой далее в книге аргументации, возможность активности подобного общего характера прямо подразумевается физическими законами, несмотря на то, что ни с чем подобным в известной физике мы еще не встречались. Некоторые примеры такой математической активности замечательно просты, поэтому представляется вполне уместным проиллюстрировать с их помо­щью то, о чем я здесь говорю.

Начать мне придется с описания нескольких примеров клас­сов хорошо структурированных математических задач, не имею­щих общего численного решения (ниже я поясню, в каком именно смысле). Начав с любого из таких классов задач, можно постро­ить «игрушечную модель» физической вселенной, активность ко­торой (хотя и будучи полностью детерминированной) фактически не поддается численному моделированию.

Первый пример такого класса задач знаменит более осталь­ных и известен под названием «десятая проблема Гильберта». Эта задача была предложена великим немецким математиком Давидом Гильбертом в 1900 году в составе этакого перечня нерешенных на тот момент математических проблем, которые по большей части определили дальнейшее развитие математики в начале (да и в конце) двадцатого века. Суть десятой проблемы Гильберта заключалась в отыскании вычислительной процеду­ры, на основании которой можно было бы определить, имеют ли уравнения, составляющие данную систему диофантовых урав­нений, хотя бы одно общее решение.

Диофантовыми называются полиномиальные уравнения с каким угодно количеством переменных, все коэффициенты и все решения которых должны быть целыми числами. (Целые числа — это числа, не имеющие дробной части, например:  Первым диофантовы уравнения систематизировал и изучил греческий математик Диофант в тре­тьем веке нашей эры.) Ниже приводится пример системы дио­фантовых уравнений:

Решением первой системы является, в частности, следующее:

тогда как вторая система вообще не имеет решения (судя по пер­вому уравнению, число у должно быть четным, судя по второму уравнению, число z также должно быть четным, однако это про­тиворечит третьему уравнению, причем при любом w, поскольку значение разности — это всегда четное число, а число 3 нечетно). Задача, поставленная Гильбертом, заключалась в отыскании математической процедуры (или алгоритма), позво­ляющей определить, какие системы диофантовых уравнений име­ют решения (наш первый пример), а какие нет (второй пример). Вспомним (см. § 1.5), что алгоритм — это всего лишь вычисли­тельная процедура, действие некоторой машины Тьюринга. Таким образом, решением десятой проблемы Гильберта является некая вычислительная процедура, позволяющая определить, когда си­стема диофантовых уравнений имеет решение.

Десятая проблема Гильберта имеет очень важное истори­ческое значение, поскольку, сформулировав ее, Гильберт поднял вопрос, который ранее не поднимался. Каков точный математиче­ский смысл словосочетания «алгоритмическое решение для клас­са задач»? Если точно, то что это вообще такое — «алгоритм»? Именно этот вопрос привел в 1936 году Алана Тьюринга к его собственному определению понятия «алгоритм», основанному на изобретенных им машинах. Примерно в то же время другие ма­тематики (Черч, Клин, Гёдель, Пост и прочие; см. [134]) пред­ложили несколько иные процедуры. Как вскоре было показано, все эти процедуры оказались эквивалентными либо определению Тьюринга, либо определению Черча, хотя особый подход Тью­ринга приобрел все же наибольшее влияние. (Только Тьюрингу пришла в голову идея специфической и всеобъемлющей алгорит­мической машины, — названной универсальной машиной Тью­ринга, — которая способна самостоятельно выполнить абсолют­но любое алгоритмическое действие. Именно эта идея привела впоследствии к созданию концепции универсального компьюте­ра, который сегодня так хорошо нам знаком.) Тьюрингу удалось показать, что существуют определенные классы задач, которые не имеют алгоритмического решения (в частности, «пробле­ма остановки», о которой я расскажу ниже). Однако самой де­сятой проблеме Гильберта пришлось ждать своего решения до 1970 года, когда русский математик Юрий Матиясевич (предста­вив доказательства, ставшие логическим завершением некоторых соображений, выдвинутых ранее американскими математиками

Джулией Робинсон, Мартином Дэвисом и Хилари Патнэмом) показал невозможность создания компьютерной программы (или алгоритма), способной систематически определять, имеет ли ре­шение та или иная система диофантовых уравнений. (См. [71] и [88], глава 6, где приводится весьма занимательное изложе­ние этой истории.) Заметим, что в случае утвердительного ответа (т. е. когда система имеет-таки решение), этот факт, в принципе, можно констатировать с помощью особой компьютерной про­граммы, которая самым тривиальным образом проверяет один за другим все возможные наборы целых чисел. Сколько-нибудь систематической обработке не поддается именно случай отсут­ствия решения. Можно, конечно, создать различные совокуп­ности правил, которые корректно определяли бы, когда систе­ма не имеет решения (наподобие приведенного выше рассужде­ния с использованием четных и нечетных чисел, исключающего возможность решения второй системы), однако, как показывает теорема Матиясевича, список таких совокупностей никогда не будет полным.

Еще одним примером класса вполне структурированных ма­тематических задач, не имеющих алгоритмического решения, яв­ляется задача о замощении. Она формулируется следующим образом: дан набор многоугольников, требуется определить, по­крывают ли они плоскость; иными словами, возможно ли по­крыть всю евклидову плоскость только этими многоугольниками без зазоров и наложений? В 1966 году американский математик Роберт Бергер показал (причем эффективно), что эта задача вы­числительными средствами неразрешима. В основу его доводов легло обобщение одной из работ американского математика ки­тайского происхождения Хао Вана, опубликованной в 1961 году (см. [175]). Надо сказать, что в моей формулировке задача ока­зывается несколько более громоздкой, чем хотелось бы, так как многоугольные плитки описываются в общем случае с помощью вещественных чисел (чисел, выражаемых в виде бесконечных де­сятичных дробей), тогда как обычные алгоритмы способны опе­рировать только целыми числами. От этого неудобства можно избавиться, если в качестве рассматриваемых многоугольников выбрать плитки, состоящие из нескольких квадратов, примыкаю­щих один к другому сторонами. Такие плитки называются полиомино (см. [ 160); [ 135], глава 13; [221 ]). На рис. 1.2 показаны неко­торые плитки полиомино и примеры замощений ими плоскости.

(Другие примеры замощений плоскости наборами плиток см. в НРК, с. 133—137, рис. 4.6—4.12.) Любопытно, что вычислитель­ная неразрешимость задачи о замощении связана с существова­нием наборов полиомино, называемых апериодическими, такие наборы покрывают плоскость исключительно апериодически (т. е. так, что никакой участок законченного узора нигде не по­вторяется, независимо от площади покрытой плиткой плоскости). На рис. 1.3 представлен апериодический набор из трех полиоми­но (полученный из набора, обнаруженного Робертом Амманом в 1977 году; см. [175], рис. 10.4.11-10.4.13 на с. 555-556).

Математические доказательства неразрешимости с помо­щью вычислительных методов десятой проблемы Гильберта и за­дачи о замощении весьма сложны, и я, разумеется, не стану и пытаться приводить их здесь). Центральное место в каждом из этих доказательств отводится, в сущности, тому, чтобы показать, каким образом можно запрограммировать машину Тьюринга на решение задачи о диофантовых уравнениях или задачи о замоще­нии. В результате все сводится к вопросу, который Тьюринг рас­сматривал еще в своем первоначальном исследовании: к вычис­лительной неразрешимости проблемы остановки — проблемы определения ситуаций, в которых работа машины Тьюринга не может завершиться. В §2.3 мы приведем несколько примеров явных вычислительных процедур, которые принципиально не мо­гут завершиться, а в § 2.5 будет представлено достаточно про­стое доказательство — основанное, по большей части, на ориги­нальном доказательстве Тьюринга — которое, помимо прочего, показывает, что проблема остановки действительно неразреши­ма вычислительными методами. (Что же касается следствий из того самого «прочего», ради которого, собственно, и затевалось упомянутое доказательство, то на них, в сущности, построены рассуждения всей первой части книги.)

Каким же образом можно применить такой класс задач, как задачи о диофантовых уравнениях или задачи о замощении, к со­зданию «игрушечной» вселенной, которая, будучи детерминиро­ванной, является, тем не менее, невычислимой? Допустим, что в нашей модели вселенной течет дискретное время, параметризо­ванное натуральными (т.е. целыми неотрицательными) числами  Предположим, что в некий момент времени п состояние вселенной точно определяется одной задачей из рас­сматриваемого класса, скажем, набором полиомино. Необходи-

мо установить два вполне определенных правила относительно того, какой из наборов полиомино будет представлять состояние вселенной в момент времени при заданном наборе полиомино для состояния вселенной в момент времени n, причем первое из этих правил применяется в том случае, если полиоми­но покрывают всю плоскость без зазоров и наложений, а вто­рое — если это не так. То, как именно будут выглядеть подоб­ные правила, не имеет в данном случае особого значения. Мож­но составить список всех возможных наборов полиомино таким образом, чтобы наборы, содержащие в общей сложности четное число квадратов, имели бы четные индексы а наборы с нечетным количеством квадратов — нечетные индексы (Составление такого списка не представляет особой сложности; нужно лишь подобрать соответствующую вычислительную процедуру.) Итак, «динамическая эволюция» нашей игрушечной вселенной задает­ся теперь следующим условием:

Из состояния в момент времени вселенная пере­ходит в момент времени в состояние , если набор полиомино покрывает плоскость, и в состо­яние если набор не покрывает плоскость.

Поведение такой вселенной полностью детерминировано, одна­ко поскольку в нашем распоряжении нет общей вычислительной процедуры, позволяющей установить, какой из наборов полио­мино покрывает плоскость (причем это верно и тогда, когда общее число квадратов постоянно, независимо от того, четное оно или нет), то невозможно и численное моделирование ее реального развития. (См. рис. 1.4.)

Безусловно, такую схему нельзя воспринимать хоть сколько-нибудь всерьез — она ни в коем случае не моделирует реаль­ную вселенную, в которой все мы живем. Эта схема приводится здесь (как, собственно, и в НРК,, с. 170) для иллюстрации то­го часто недооцениваемого факта, что между детерминизмом и вычислимостью существует вполне определенная разница. Неко­торые полностью детерминированные модели вселенной с четкими законами эволюции невозможно реализовать вы­числительными средствами. Вообще говоря, как мы убедимся в § 7.9, только что рассмотренные мною весьма специфические модели не совсем отвечают реальным требованиям точки зре-

ния . Что же касается тех феноменов, которые отвечают-таки этим самым реальным требованиям, и некоторых связанных с упомянутыми феноменами поразительных физических возмож­ностях, то о них мы поговорим в

Из всех типов вполне определенных процессов, что приходят в голову, большая часть относится, соответственно, к категории феноменов, называемых мною «вычислительными» (имеются в виду, конечно же, «цифровые вычисления»). Возможно, читатель уже начал волноваться, что сторонники позиции так и оста­нутся у нас не при деле. Причем я еще ни словом не упоминал о строго случайных процессах, которые могут быть обуслов­лены, скажем, какими-либо исходными данными, получаемыми от квантовой системы. (О квантовой механике мы немного по­дробнее поговорим во второй части, главы 5 и 6.) Впрочем, для самой системы практически безразлично, подается на ее вход подлинно случайная последовательность данных или же всего лишь псевдослучайная, которую можно целиком и полностью сгенерировать вычислительным путем (см. §3.11). Действитель­но, несмотря на то, что между «случайным» и «псевдослучай­ным», строго говоря, существуют некоторые формальные отли­чия, они, на первый взгляд, не имеют непосредственного отно­шения к проблемам ИИ. Далее, в §3.11, §3.18 и последующих, я приведу некоторые серьезные доводы в пользу того, что «чистая случайность» и в самом деле абсолютно бесполезна для наших целей; если уж возникает такая необходимость, то лучше все же придерживаться псевдослучайности хаотического поведения, а все нормальные типы хаотического поведения, как уже подчер­кивалось выше, относятся к категории «вычислительных».

А что нам известно о роли окружения? По мере развития каждого индивидуума у него или у нее формируется уникаль­ное окружение, отличное от окружения любого другого человека. Возможно, именно это уникальное личное окружение и дает каж­дому из нас ту особенную последовательность входных данных, которая неподвластна вычислению? Хотя лично мне, например, сложно сообразить, на что именно в данном контексте может повлиять «уникальность» нашего окружения. Эти рассуждения напоминают разговор о хаосе, который мы вели выше (см. § 1.7). Для обучения управляемого компьютером робота достаточно од­ной лишь модели некоего правдоподобного окружения (хаоти­ческого), при том, разумеется, условии, что в этой модели не будет ничего заведомо невычислимого. Роботу нет нужды учиться тем или иным навыкам в каком-то конкретном реальном окружении; его, разумеется, вполне устроит типичное окружение, модели­рующее реальность вычислительными методами.

А может быть, численное моделирование пусть даже все­го лишь правдоподобного окружения невозможно в принципе. Быть может, в окружающем физическом мире есть-таки нечто такое, что на самом деле неподвластно численному моделиро­ванию. Возможно, некоторые сторонники уже воз­намерились приписать все не поддающиеся, на первый взгляд, вычислению проявления человеческого поведения невычислимо­сти внешнего окружения. Должен, однако, заметить, что намере­ние это несколько опрометчиво. Ибо, как только мы признаем, что физическое поведение допускает где-то что-то такое, что невозможно моделировать вычислительными методами, мы тем самым тут же лишаемся главного, по всей видимости, основания сомневаться в правдоподобии, в первую очередь, самой точки зрения . Если во внешнем окружении (т.е. вне мозга) имеют место процессы, не поддающиеся численному моделированию, то почему не могут оказаться таковыми и процессы, протекающие внутри мозга? В конце концов, внутренняя физическая органи­зация мозга человека, по всей видимости, гораздо более сложна, чем большая часть (и это еще слабо сказано) его окружения, за исключением, быть может, тех его участков, где это окружение само оказывается под сильным влиянием деятельности других

мозгов. Признание возможности внешней невычислимой физи­ческой активности лишает всякой силы главный аргумент про­тив . (См. также §3.9, §3.10.)

Следует сделать еще одно замечание относительно «не под­дающихся вычислению» процессов, возможность существования которых предполагает позиция . Под этим термином я имею в виду отнюдь не те процессы, которые всего-навсего невычис­лимы практически. Здесь, конечно же, уместно вспомнить и о том, что, хотя моделирование любого правдоподобного окру­жения, или же любое точное воспроизведение всех физических и химических процессов, протекающих в мозге, может быть, в принципе, вычислимым, на такое вычисление, скорее всего, по­надобится столько времени или такой объем памяти, что вряд ли удастся выполнить его на любом реально существующем или даже вообразимом в ближайшем будущем компьютере. Вероят­но, нереально даже написание соответствующей компьютерной программы, если учесть, какое огромное количество различных факторов придется принимать в расчет. Однако сколь бы суще­ственными ни были все эти соображения (а мы еще вернемся к ним в они не имеют никакого отношения к тому, что называю «невычислимостью» я (и чего требует ). Под «невычислимостью» я подразумеваю принципиальную невоз­можность вычисления в том смысле, который мы очень скоро об­судим. Вычисления, которые просто выходят за рамки существу­ющих или вообразимых компьютеров, или имеющихся в нашем распоряжении вычислительных методов, формально все равно остаются «вычислениями».

Читатель имеет полное право спросить: если ничего, что можно счесть «невычислимым», не обнаруживается ни в случай­ности, ни во влиянии окружения, ни в банальном несоответствии уровня сложности феномена нашим техническим возможностям, то что вообще я имею в виду, говоря «чего требует »? В общем случае, это некий вид математически точной активности, невы­числимость которой можно доказать. Насколько нам на данный момент известно, при описании физического поведения в подоб­ной математической активности необходимости не возникает. Тем не менее, логически она возможна. Более того, она представляет собой нечто большее, нежели просто логическую возможность. Согласно приводимой далее в книге аргументации, возможность активности подобного общего характера прямо подразумевается физическими законами, несмотря на то, что ни с чем подобным в известной физике мы еще не встречались. Некоторые примеры такой математической активности замечательно просты, поэтому представляется вполне уместным проиллюстрировать с их помо­щью то, о чем я здесь говорю.

Начать мне придется с описания нескольких примеров клас­сов хорошо структурированных математических задач, не имею­щих общего численного решения (ниже я поясню, в каком именно смысле). Начав с любого из таких классов задач, можно постро­ить «игрушечную модель» физической вселенной, активность ко­торой (хотя и будучи полностью детерминированной) фактически не поддается численному моделированию.

Первый пример такого класса задач знаменит более осталь­ных и известен под названием «десятая проблема Гильберта». Эта задача была предложена великим немецким математиком Давидом Гильбертом в 1900 году в составе этакого перечня нерешенных на тот момент математических проблем, которые по большей части определили дальнейшее развитие математики в начале (да и в конце) двадцатого века. Суть десятой проблемы Гильберта заключалась в отыскании вычислительной процеду­ры, на основании которой можно было бы определить, имеют ли уравнения, составляющие данную систему диофантовых урав­нений, хотя бы одно общее решение.

Диофантовыми называются полиномиальные уравнения с каким угодно количеством переменных, все коэффициенты и все решения которых должны быть целыми числами. (Целые числа — это числа, не имеющие дробной части, например:  Первым диофантовы уравнения систематизировал и изучил греческий математик Диофант в тре­тьем веке нашей эры.) Ниже приводится пример системы дио­фантовых уравнений:

Решением первой системы является, в частности, следующее:

тогда как вторая система вообще не имеет решения (судя по пер­вому уравнению, число у должно быть четным, судя по второму уравнению, число z также должно быть четным, однако это про­тиворечит третьему уравнению, причем при любом w, поскольку значение разности — это всегда четное число, а число 3 нечетно). Задача, поставленная Гильбертом, заключалась в отыскании математической процедуры (или алгоритма), позво­ляющей определить, какие системы диофантовых уравнений име­ют решения (наш первый пример), а какие нет (второй пример). Вспомним (см. § 1.5), что алгоритм — это всего лишь вычисли­тельная процедура, действие некоторой машины Тьюринга. Таким образом, решением десятой проблемы Гильберта является некая вычислительная процедура, позволяющая определить, когда си­стема диофантовых уравнений имеет решение.

Десятая проблема Гильберта имеет очень важное истори­ческое значение, поскольку, сформулировав ее, Гильберт поднял вопрос, который ранее не поднимался. Каков точный математиче­ский смысл словосочетания «алгоритмическое решение для клас­са задач»? Если точно, то что это вообще такое — «алгоритм»? Именно этот вопрос привел в 1936 году Алана Тьюринга к его собственному определению понятия «алгоритм», основанному на изобретенных им машинах. Примерно в то же время другие ма­тематики (Черч, Клин, Гёдель, Пост и прочие; см. [134]) пред­ложили несколько иные процедуры. Как вскоре было показано, все эти процедуры оказались эквивалентными либо определению Тьюринга, либо определению Черча, хотя особый подход Тью­ринга приобрел все же наибольшее влияние. (Только Тьюрингу пришла в голову идея специфической и всеобъемлющей алгорит­мической машины, — названной универсальной машиной Тью­ринга, — которая способна самостоятельно выполнить абсолют­но любое алгоритмическое действие. Именно эта идея привела впоследствии к созданию концепции универсального компьюте­ра, который сегодня так хорошо нам знаком.) Тьюрингу удалось показать, что существуют определенные классы задач, которые не имеют алгоритмического решения (в частности, «пробле­ма остановки», о которой я расскажу ниже). Однако самой де­сятой проблеме Гильберта пришлось ждать своего решения до 1970 года, когда русский математик Юрий Матиясевич (предста­вив доказательства, ставшие логическим завершением некоторых соображений, выдвинутых ранее американскими математиками

Джулией Робинсон, Мартином Дэвисом и Хилари Патнэмом) показал невозможность создания компьютерной программы (или алгоритма), способной систематически определять, имеет ли ре­шение та или иная система диофантовых уравнений. (См. [71] и [88], глава 6, где приводится весьма занимательное изложе­ние этой истории.) Заметим, что в случае утвердительного ответа (т. е. когда система имеет-таки решение), этот факт, в принципе, можно констатировать с помощью особой компьютерной про­граммы, которая самым тривиальным образом проверяет один за другим все возможные наборы целых чисел. Сколько-нибудь систематической обработке не поддается именно случай отсут­ствия решения. Можно, конечно, создать различные совокуп­ности правил, которые корректно определяли бы, когда систе­ма не имеет решения (наподобие приведенного выше рассужде­ния с использованием четных и нечетных чисел, исключающего возможность решения второй системы), однако, как показывает теорема Матиясевича, список таких совокупностей никогда не будет полным.

Еще одним примером класса вполне структурированных ма­тематических задач, не имеющих алгоритмического решения, яв­ляется задача о замощении. Она формулируется следующим образом: дан набор многоугольников, требуется определить, по­крывают ли они плоскость; иными словами, возможно ли по­крыть всю евклидову плоскость только этими многоугольниками без зазоров и наложений? В 1966 году американский математик Роберт Бергер показал (причем эффективно), что эта задача вы­числительными средствами неразрешима. В основу его доводов легло обобщение одной из работ американского математика ки­тайского происхождения Хао Вана, опубликованной в 1961 году (см. [175]). Надо сказать, что в моей формулировке задача ока­зывается несколько более громоздкой, чем хотелось бы, так как многоугольные плитки описываются в общем случае с помощью вещественных чисел (чисел, выражаемых в виде бесконечных де­сятичных дробей), тогда как обычные алгоритмы способны опе­рировать только целыми числами. От этого неудобства можно избавиться, если в качестве рассматриваемых многоугольников выбрать плитки, состоящие из нескольких квадратов, примыкаю­щих один к другому сторонами. Такие плитки называются полиомино (см. [ 160); [ 135], глава 13; [221 ]). На рис. 1.2 показаны неко­торые плитки полиомино и примеры замощений ими плоскости.

(Другие примеры замощений плоскости наборами плиток см. в НРК, с. 133—137, рис. 4.6—4.12.) Любопытно, что вычислитель­ная неразрешимость задачи о замощении связана с существова­нием наборов полиомино, называемых апериодическими, такие наборы покрывают плоскость исключительно апериодически (т. е. так, что никакой участок законченного узора нигде не по­вторяется, независимо от площади покрытой плиткой плоскости). На рис. 1.3 представлен апериодический набор из трех полиоми­но (полученный из набора, обнаруженного Робертом Амманом в 1977 году; см. [175], рис. 10.4.11-10.4.13 на с. 555-556).

Математические доказательства неразрешимости с помо­щью вычислительных методов десятой проблемы Гильберта и за­дачи о замощении весьма сложны, и я, разумеется, не стану и пытаться приводить их здесь). Центральное место в каждом из этих доказательств отводится, в сущности, тому, чтобы показать, каким образом можно запрограммировать машину Тьюринга на решение задачи о диофантовых уравнениях или задачи о замоще­нии. В результате все сводится к вопросу, который Тьюринг рас­сматривал еще в своем первоначальном исследовании: к вычис­лительной неразрешимости проблемы остановки — проблемы определения ситуаций, в которых работа машины Тьюринга не может завершиться. В §2.3 мы приведем несколько примеров явных вычислительных процедур, которые принципиально не мо­гут завершиться, а в § 2.5 будет представлено достаточно про­стое доказательство — основанное, по большей части, на ориги­нальном доказательстве Тьюринга — которое, помимо прочего, показывает, что проблема остановки действительно неразреши­ма вычислительными методами. (Что же касается следствий из того самого «прочего», ради которого, собственно, и затевалось упомянутое доказательство, то на них, в сущности, построены рассуждения всей первой части книги.)

Каким же образом можно применить такой класс задач, как задачи о диофантовых уравнениях или задачи о замощении, к со­зданию «игрушечной» вселенной, которая, будучи детерминиро­ванной, является, тем не менее, невычислимой? Допустим, что в нашей модели вселенной течет дискретное время, параметризо­ванное натуральными (т.е. целыми неотрицательными) числами  Предположим, что в некий момент времени п состояние вселенной точно определяется одной задачей из рас­сматриваемого класса, скажем, набором полиомино. Необходи-

мо установить два вполне определенных правила относительно того, какой из наборов полиомино будет представлять состояние вселенной в момент времени при заданном наборе полиомино для состояния вселенной в момент времени n, причем первое из этих правил применяется в том случае, если полиоми­но покрывают всю плоскость без зазоров и наложений, а вто­рое — если это не так. То, как именно будут выглядеть подоб­ные правила, не имеет в данном случае особого значения. Мож­но составить список всех возможных наборов полиомино таким образом, чтобы наборы, содержащие в общей сложности четное число квадратов, имели бы четные индексы а наборы с нечетным количеством квадратов — нечетные индексы (Составление такого списка не представляет особой сложности; нужно лишь подобрать соответствующую вычислительную процедуру.) Итак, «динамическая эволюция» нашей игрушечной вселенной задает­ся теперь следующим условием:

Из состояния в момент времени вселенная пере­ходит в момент времени в состояние , если набор полиомино покрывает плоскость, и в состо­яние если набор не покрывает плоскость.

Поведение такой вселенной полностью детерминировано, одна­ко поскольку в нашем распоряжении нет общей вычислительной процедуры, позволяющей установить, какой из наборов полио­мино покрывает плоскость (причем это верно и тогда, когда общее число квадратов постоянно, независимо от того, четное оно или нет), то невозможно и численное моделирование ее реального развития. (См. рис. 1.4.)

Безусловно, такую схему нельзя воспринимать хоть сколько-нибудь всерьез — она ни в коем случае не моделирует реаль­ную вселенную, в которой все мы живем. Эта схема приводится здесь (как, собственно, и в НРК,, с. 170) для иллюстрации то­го часто недооцениваемого факта, что между детерминизмом и вычислимостью существует вполне определенная разница. Неко­торые полностью детерминированные модели вселенной с четкими законами эволюции невозможно реализовать вы­числительными средствами. Вообще говоря, как мы убедимся в § 7.9, только что рассмотренные мною весьма специфические модели не совсем отвечают реальным требованиям точки зре-

ния . Что же касается тех феноменов, которые отвечают-таки этим самым реальным требованиям, и некоторых связанных с упомянутыми феноменами поразительных физических возмож­ностях, то о них мы поговорим в