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

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

тогда как вторая система вообще не имеет решения (судя по пер­вому уравнению, число у должно быть четным, судя по второму уравнению, число 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, только что рассмотренные мною весьма специфические модели не совсем отвечают реальным требованиям точки зре-

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

1.10. Завтрашний день

Так какого же будущего для этой планеты нам следует ожи­дать согласно точкам зрения .  Если верить то настанет время, когда соответствующим образом запрограмми­рованные суперкомпьютеры догонят — а затем и перегонят человека во всех его интеллектуальных достижениях. Конечно же, сторонники придерживаются различных взглядов отно­сительно необходимого для этого времени. Некоторые вполне разумно полагают, что пройдет еще много столетий, прежде чем компьютеры достигнут уровня человека, принимая во внимание крайнюю скудость современного понимания реально выполня­емых мозгом вычислений (так они говорят), обусловливающих ту тонкость поведения, какую, несомненно, демонстрирует человек, — тонкость, без которой, конечно же, нельзя говорить о ка­ком бы то ни было «пробуждении сознания». Другие утверждают, что времени понадобится значительно меньше. В частности, Ханс Моравек в своей книге «Дети разума» [266] приводит вполне аргументированное доказательство (основанное на непрерывно ускоряющемся развитии компьютерных технологий за послед­ние пятьдесят лет и на своей оценке той доли от всего объема функциональной активности мозга, которая на сегодняшний день уже успешно моделируется численными методами) в поддержку своего утверждения, будто уровень «эквивалентности человеку» будет преодолен уже к 2030 году. (Кое-кто утверждает, что это время будет еще короче), а кто-то даже уверен, что предска­занная дата достижения эквивалентности человеку уже осталась в прошлом!) Однако чтобы читатель не очень пугался того, что менее чем через сорок (или около того) лет компьютеры во всем его превзойдут, горькая пилюля подслащена одной радужной на­деждой (подаваемой под видом гарантированного обещания): все мы сможем тогда перенести свои «ментальные программы» в сверкающие металлические (или пластиковые) корпуса роботов (конкретную модель, разумеется, каждый выберет себе сам), чем и обеспечим себе что-то вроде бессмертия [266, 267].

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