Тени разума. В поисках науки о сознании
Шрифт:
Начать мне придется с описания нескольких примеров классов хорошо структурированных математических задач, не имеющих общего численного решения (ниже я поясню, в каком именно смысле). Начав с любого из таких классов задач, можно построить «игрушечную» модель физической вселенной, активность которой (даже будучи полностью детерминированной) фактически не поддается численному моделированию.
Первый пример такого класса задач знаменит более остальных и известен под названием «десятая проблема Гильберта». Эта задача была предложена великим немецким математиком Давидом Гильбертом в 1900 году в составе этакого перечня нерешенных на тот момент математических проблем, которые по большей части определили дальнейшее развитие математики в начале (да и в конце) двадцатого века. Суть десятой проблемы Гильберта заключалась в отыскании вычислительной процедуры, на основании которой можно было бы определить, имеют ли уравнения, составляющие данную систему диофантовых уравнений, хотя бы одно общее решение.
Диофантовыми называются полиномиальные уравнения с каким угодно количеством переменных, все коэффициенты и все решения которых должны быть целыми числами. (Целые числа — это числа, не имеющие дробной части, например: …, -3, -2, -1, 0, 1, 2, 3, 4, …. Первым такие уравнения систематизировал и изучил греческий математик Диофант в третьем веке нашей эры.) Ниже приводится пример системы
6 + 2x 2– y 3= 0, 5xy - z 2+ 6 = 0, 2– + 2x - y + z - 4 = 0
Вот еще один пример:
6 + 2x 2– y 3= 0, 5xy - z 2+ 6 = 0, 2– + 2x - y + z - 3 = 0.
Решением первой системы является, в частности, следующее:
= 1, x= l, у= 2, z= 4,
тогда как вторая система вообще не имеет решения (судя по первому уравнению, число у должно быть четным, судя по второму уравнению, число zтакже должно быть четным, однако это противоречит третьему уравнению, причем при любом , поскольку значение разности 2– — это всегда четное число, а число 3 нечетно). Задача, поставленная Гильбертом, заключалась в отыскании математической процедуры (или алгоритма), позволяющей определить, какие системы диофантовых уравнений имеют решения (наш первый пример), а какие нет (второй пример). Вспомним (см. §1.5 ). что алгоритм — это всего лишь вычислительная процедура, действие некоторой машины Тьюринга. Таким образом, решением десятой проблемы Гильберта является некая вычислительная процедура, позволяющая определить, когда система диофантовых уравнений имеет решение.
Десятая проблема Гильберта имеет очень важное историческое значение, поскольку, сформулировав ее, Гильберт поднял вопрос, который ранее не поднимался. Каков точный математический смыслсловосочетания «алгоритмическое решение для класса задач»? Если точно, то что это вообще такое — «алгоритм»? Именно этот вопрос привел в 1936 году Алана Тьюринга к его собственному определению понятия «алгоритм», основанному на изобретенных им машинах. Примерно в то же время другие математики (Черч, Клин, Гёдель, Пост и др.; см. [ 135 ]) предложили несколько иные процедуры. Как вскоре было показано, все эти процедуры оказались эквивалентными либо определению Тьюринга, либо определению Черча, хотя особый подход Тьюринга приобрел все же наибольшее влияние. (Только Тьюрингу пришла в голову идея специфической и всеобъемлющей алгоритмической машины, — названной универсальноймашиной Тьюринга, — которая способна самостоятельно выполнить абсолютно любоеалгоритмическое действие. Именно эта идея привела впоследствии к созданию концепции универсального компьютера, который сегодня так хорошо нам знаком.) Тьюрингу удалось показать, что существуют определенные классы задач, которые не имеюталгоритмического решения (в частности, «проблема остановки», о которой я расскажу ниже). Однако самой десятой проблеме Гильберта пришлось ждать своего решения до 1970 года, когда русский математик Юрий Матиясевич (представив доказательства, ставшие логическим завершением некоторых соображений, выдвинутых ранее американскими математиками Джулией Робинсон, Мартином Дэвисом и Хилари Патнэмом) показал невозможность создания компьютерной программы (или алгоритма), способной систематически определять, имеет ли решение та или иная система диофантовых уравнений. (См. [ 72 ] и [ 89 ], глава 6, где приводится весьма занимательное изложение этой истории.) Заметим, что в случае утвердительного ответа (т.е. когда система имеет-таки решение), этот факт, в принципе, можно констатировать с помощью особой компьютерной программы, которая самым тривиальным образом проверяет один за другим все возможные наборы целых чисел. Сколько-нибудь систематической обработке не поддается именно случай отсутствия решения. Можно, конечно, создать различные совокупности правил, которые корректно определяли бы, когда система не имеет решения (наподобие приведенного выше рассуждения с использованием четных и нечетных чисел, исключающего возможность решения второй системы), однако, как показывает теорема Матиясевича, список таких совокупностей никогдане будет полным.
Еще одним примером класса вполне структурированных математических задач, не имеющих алгоритмического решения, является задача о замощении. Она формулируется следующим образом: дан набор многоугольников, требуется определить, покрывают ли они плоскость; иными словами, возможно ли покрыть всю евклидову плоскость только этими многоугольниками без зазоров и наложений? В 1966 году американский математик Роберт Бергер показал (причем эффективно), что эта задача вычислительными средствами неразрешима. В основу его доводов легло обобщение одной из работ американского математика китайского происхождения Хао Вана, опубликованной в 1961 году (см. [ 176 ]). Надо сказать, что в моей формулировке задача оказывается несколько более громоздкой, чем хотелось бы, так как многоугольные плитки описываются в общем случае с помощью вещественных чисел (чисел, выражаемых в виде бесконечных десятичных дробей), тогда как обычные алгоритмы способны оперировать только целыми числами. От этого неудобства можно избавиться, если в качестве рассматриваемых многоугольников выбрать плитки, состоящие из нескольких квадратов, примыкающих один к другому сторонами. Такие плитки называются полиомино(см. [ 161 ]; [ 136 ], глава 13; [ 222 ]). На рис. 1.2 показаны некоторые плитки полиомино и примеры замощений ими плоскости. (Другие примеры замощений плоскости наборами плиток см. в НРК, с. 133-137, рис. 4.6-4.12.) Любопытно, что вычислительная неразрешимость задачи о замощении связана с существованием наборов полиомино, называемых апериодическими; такие наборы покрывают плоскость исключительно апериодически(т.е. так, что никакой участок законченного узора нигде не повторяется, независимо от площади покрытой плиткой плоскости). На рис. 1.3 представлен апериодический набор из трех полиомино (полученный из набора, обнаруженного Робертом Амманом в 1977 году; см. [ 176 ], рис. 10.4.11-10.4.13 на с. 555-556).
Математические доказательства неразрешимости с помощью вычислительных методов десятой проблемы Гильберта и задачи о замощении весьма сложны, и я, разумеется, не стану и пытаться приводить их здесь {13} . Центральное место в каждом из
Рис. 1.2. Плитки полиомино и замощения ими бесконечной евклидовой плоскости (допускается использование зеркально отраженных плиток). Если брать полиомино из набора (с) по отдельности, то ни одно из них не покроет всю плоскость.
Рис. 1.З. Набор из трех полиомино, покрывающий плоскость апериодически (получен из набора Роберта Аммана).
Каким же образом можно применить такой класс задач, как задачи о диофантовых уравнениях или задачи о замощении, к созданию «игрушечной» вселенной, которая, будучи детерминированной, является, тем не менее, невычислимой? Допустим, что в нашей модели вселенной течет дискретноевремя, параметризованное натуральными (т.е. целыми неотрицательными) числами 0, 1, 2, 3, 4, …. Предположим, что в некий момент времени nсостояние вселенной точно определяется одной задачей из рассматриваемого класса, скажем, набором полиомино. Необходимо установить два вполне определенных правила относительно того, какой из наборов полиомино будет представлять состояние вселенной в момент времени n+ 1 при заданном наборе полиомино для состояния вселенной в момент времени n, причем первое из этих правил применяется в том случае, если полиомино покрываютвсю плоскость без зазоров и наложений, а второе — если это не так. То, как именно будут выглядеть подобные правила, не имеет в данном случае особого значения. Можно составить список S 0, S 1, S 2, S 3, S 4, S 5, … всех возможных наборов полиомино таким образом, чтобы наборы, содержащие в общей сложности четноечисло квадратов, имели бы четные индексы S 0, S 2, S 4, S 6, …, а наборы с нечетнымколичеством квадратов — нечетные индексы S 1, S 3, S 5, S 7, …. (Составление такого списка не представляет особой сложности; нужно лишь подобрать соответствующую вычислительную процедуру.) Итак, «динамическая эволюция» нашей игрушечной вселенной задается теперь следующим условием:
Из состояния S nв момент времени tвселенная переходит в момент времени t+ 1 в состояние S n +1, если набор полиомино S nпокрывает плоскость, и в состояние S n+2, если набор S nне покрываетплоскость.
Поведение такой вселенной полностью детерминировано, однако поскольку в нашем распоряжении нет общей вычислительной процедуры, позволяющей установить, какой из наборов полиомино Sn покрывает плоскость (причем это верно и тогда, когда общее число квадратов постоянно, независимо от того, четное оно или нет), то невозможно и численное моделирование ее реального развития. (См. рис. 1.4 .)
Рис. 1.4. Невычислимая модель «игрушечной» вселенной. Различные состояния этой детерминированной, но невычислимой вселенной даны в виде возможных конечных наборов полиомино, пронумерованных таким образом, что четные индексы S nсоответствуют четному общему количеству квадратов в наборе, а нечетные индексы — нечетному количеству квадратов. Временная эволюция происходит в порядке увеличения индекса ( S 0, S 2, S 3, S 4, …, S 278, S 280, …), при этом индекс пропускается, когда предыдущий набор оказывается не в состоянии замостить плоскость.
Безусловно, такую схему нельзя воспринимать хоть сколько-нибудь всерьез — она ни в коем случае не моделирует реальную вселенную, в которой все мы живем. Эта схема приводится здесь (как, собственно, и в НРК, с. 170) для иллюстрации того часто недооцениваемого факта, что между детерминизмом и вычислимостью существует вполне определенная разница. Некоторые полностью детерминированные модели вселенной с четкими законами эволюции невозможно реализовать вычислительными средствами. Вообще говоря, как мы убедимся в §7.9 , только что рассмотренные мною весьма специфические модели не совсем отвечают реальным требованиям точки зрения C. Что же касается тех феноменов, которые отвечают-таки этим самым реальным требованиям, и некоторых связанных с упомянутыми феноменами поразительных физических возможностях, то о них мы поговорим в §7.10 .