Противоречит ли точка зрения В тезису Черча—Тьюринга?
Вспомним, что точка зрения предполагает, что обладающий сознанием мозг функционирует таким образом, что его активность не поддается никакому численному моделированию — ни нисходящего, ни восходящего, ни какого-либо другого типа. Те, кто сомневается в истинности
могут отчасти оправдать свои сомнения тем, что формулировка
якобы противоречит так называемому тезису Черча (или тезису Черча—Тьюринга) — вернее, тому условию, которое сейчас общепринято обозначать упомянутым термином. В чем же суть тезиса Черча? В первоначальной форме, предложенной американским логиком Алонзо Черчем в 1936 году, этот тезис гласил, что любой процесс, который можно корректно назвать «чисто механическим» математическим процессом, — т.е. любой алгоритмический процесс — может быть реализован в рамках конкретной схемы, открытой самим Черчем и названной им лямбда-исчислением (
-исчислением) (весьма, надо отметить, изящная и концептуально сдержанная схема; краткое ознакомительное изложение см. в НРК, с. 66—70). Вскоре после этого, в 1936—1937 годах, британский математик Алан Тьюринг нашел свой собственный, гораздо более убедительный способ описания алгоритмических процессов, основанный на функционировании теоретических «вычислительных машин», которые мы сейчас называем машинами Тьюринга. Вслед за Тьюрингом в некоторой степени аналогичную схему разработал американский ученый-логик польского происхождения Эмиль Пост( 1936). Далее Черч и Тьюринг независимо друг от друга показали, что исчисление Черча эквивалентно концепции машины Тьюринга (а следовательно, и схемы Поста). Более того, именно этим концепциям Тьюринга в значительной степени обязаны своим появлением на светсовременные универсальные компьютеры. Как уже упоминалось, машина Тьюринга по принципу функционирования фактически полностью эквивалентна современному компьютеру, — несколько, впрочем, идеализированному, т. е. обладающему возможностью использовать неограниченный объем памяти. Таким образом получается, что тезис Черча в его первоначальной формулировке всего лишь утверждает, что математическими алгоритмами следует считать как раз те процессы, которые способен выполнить идеализированный современный компьютер — а если учесть общепринятое ныне определение термина «алгоритм», то такое утверждение и вовсе становится тавтологией. Так что принятие этой формулировки тезиса Черча не влечет за собой никакого противоречия точке зрения
Вполне вероятно, однако, что сам Тьюринг имел в виду нечто большее: вычислительные возможности любого физического устройства должны (в идеале) быть эквивалентны действию машины Тьюринга. Такое утверждение существенно выходит за рамки того, что изначально подразумевал Черч. При разработке концепции «машины Тьюринга» сам Тьюринг основывался на своих представлениях о том, чего, в принципе, мог бы достичь вычислитель-человек (см. [197]). Судя по всему, он полагал, что физическое действие в общем (а под эту категорию подпадает и активность мозга человека) всегда можно свести к какой-либо разновидности действия машины Тьюринга. Быть может, это утверждение (физическое) следует называть «тезисом Тьюринга» — для того чтобы отличать его от оригинального «тезиса Черча», утверждения чисто математического, которому никоим образом не противоречит Именно такой терминологии я намерен придерживаться далее в этой книге. Соответственно, точка зрения
противоречит в этом случае тезису Тьюринга, а вовсе не тезису Черча.
Хаос
В последние годы ученые проявляют огромный интерес к математическому феномену, известному под названием «хаос», — феномену, в рамках которого физические системы оказываются способными на якобы аномальное и непредсказуемое поведение (рис. 1.1). Образует ли феномен хаоса необходимую невычислимую физическую основу для такой точки зрения, как ?
Хаотические системы — это динамически развивающиеся физические системы, математические модели таких физических систем или же просто математические модели, не описывающие никакой реальной физической системы и интересные сами по себе; характерно то, что будущее поведение такой системы чрезвычайно сильно зависит от ее начального состояния, причем определяющими могут оказаться самые незначительные факторы. Хотя обыкновенные хаотические системы являются полностью детерминированными и вычислительными, на деле может показаться, что в их поведении ничего детерминированного нет и никогда не было. Это происходит потому, что для сколько-нибудь надежного детерминистического предсказания будущего поведения системы необходимо знать ее начальное состояние с такой точностью, которая может оказаться просто недостижимой не только для тех измерительных средств, которыми мы располагаем, но также и для тех, которые мы только можем вообразить.
В этой связи чаще всего вспоминают о подробных долгосрочных прогнозах погоды. Законы, управляющие движением молекул воздуха, а также другими физическими величинами, которые могут оказаться релевантными для определения будущей погоды, хорошо известны. Однако реальные синоптические ситуации, которые могут возникнуть всего через несколько дней после предсказания, настолько тонко зависят от начальных условий, что нет никакой возможности измерить эти условия достаточно точно для того, чтобы дать хоть сколько-нибудь надежный прогноз. Безусловно, количество параметров, которые необходимо ввести в подобное вычисление, огромно; поэтому, быть может, и нет ничего удивительного в том, что в данном случае предсказание может оказаться на практике просто невозможным.
С другой стороны, подобное — так называемое хаотическое — поведение может иметь место и в случае очень простых систем; примером тому служат системы, состоящие из малого количества частиц. Вообразите, что от вас требуется загнать в лузу бильярдный шар Е, расположенный пятым в некоторой извилистой и очень растянутой цепочке шаров ; вам нужно ударить кием по шару А так, чтобы тот ударил шар В, который, в свою очередь, ударил бы шар С, который ударил бы шар D, который ударил бы шар Е, который, наконец, попал бы в лузу. В общем случае необходимая для этого точность значительно превышает способности любого профессионального игрока в бильярд. Если бы цепочка состояла из 20 шаров, то тогда — даже допустив, что эти шары представляют собой идеально упругие точные сферы — задача загнать в лузу последний шар оказалась бы не под силу и самому точному механизму из всех доступных современной технологии. Поведение последних шаров цепочки было бы, в сущности, случайным, несмотря на то, что управляющие поведением шаров ньютоновы законы математически абсолютно детерминированы и, в принципе, эффективно вычислимы. Никакое вычисление не смогло бы предсказать реальное поведение последних шаров цепочки просто потому, что нет никакой возможности добиться достаточно точного определения реального начального положения и скорости движения кия или положений первых шаров цепочки. Более того, даже самые незначительные внешние воздействия, вроде дыхания человека в соседнем городе, могут нарушить эту точность до такой степени, которая полностью обесценит результаты любого подобного вычисления.
Здесь необходимо пояснить, что, несмотря на столь серьезные трудности, встающие перед детерминистическим предсказанием, все нормальные системы, к которым применим термин «хаотические», следует относить к категории систем, которые я называю «вычислительными». Почему? Как и в других ситуациях, которые мы рассмотрим позднее, для того, чтобы определить, является ли та или иная процедура вычислительной, достаточно задать себе вопрос: выполнима ли она на обычном универсальном компьютере? Очевидно, что в данном случае ответ может быть только утвердительным, по той простой причине, что математически описываемые хаотические системы и в самом деле изучаются, как правило, с помощью компьютера!
Разумеется, если мы попытаемся создать компьютерную модель для подробного предсказания погоды в Европе в течение недели или же для описания последовательных столкновений расположенных вдоль некоторой кривой на достаточно большом расстоянии друг от друга двадцати бильярдных шаров после того, как по первому из них резко ударили кием, то можно почти с полной определенностью утверждать, что результаты, полученные с помощью нашей модели, и близко не будут похожи на то, что произойдет в действительности. Такова природа хаотических систем. На практике бесполезно пытаться с помощью вычислений предсказать реальное конечное состояние системы. Тем не менее, моделирование типичного конечного состояния вполне возможно. Предсказанная погода может и не совпасть с реальной, но она абсолютно правдоподобна как погода вообще! Точно так же и предсказанный результат столкновений бильярдных шаров абсолютно приемлем как возможный исход, даже несмотря на то, что на самом деле шары могут повести себя совершенно не так, как предсказано вычислением, — однако и при этом их поведение остается в равной степени приемлемым. Упомянем еще об одном обстоятельстве, которое подчеркивает идеально вычислительную природу таких операций: если запустить процесс компьютерного моделирования вторично, задав те же входные
данные, что и ранее, то результат моделирования будет точно таким же, как и в первый раз! (Здесь предполагается, что сам компьютер не ошибается; впрочем, надо признать, что современные компьютеры и в самом деле крайне редко совершают при вычислениях реальные ошибки.)
Возвращаясь к искусственному интеллекту, отметим, что никто пока и не пытается воспроизвести поведение какого-то конкретного индивидуума; нас бы прекрасно устроила модель индивидуума вообще! В этом контексте моя позиция вовсе не представляется такой уж неразумной: хаотические системы следует безусловно относить к категории систем, которые мы называем «вычислительными». Компьютерная модель такой системы и в самом деле выглядела бы как абсолютно приемлемый «типичный случай», даже и не совпадая при этом ни с каким «реальным случаем». Если внешние проявления человеческого разума суть результаты некоей хаотической динамической эволюции (эволюции вычислительной в том смысле, о котором мы только что говорили), то это вполне согласуется с точками зрения , но никак не
Время от времени выдвигаются предположения, что, возможно, именно феномен хаоса — если, конечно, он действительно имеет место в деятельности мозга как физической сущности — позволяет человеческому мозгу симулировать поведение, якобы отличное от вычислительно-детерминированного функционирования машины Тьюринга, хотя, как подчеркивалось выше, формально его активность является целиком и полностью вычислительной. К этому вопросу мне еще придется вернуться несколько позднее . Пока же достаточно уяснить лишь то, что хаотические системы относятся к категории систем, называемых мною «вычислительными» или «алгоритмическими». Вопрос же о том, можно ли смоделировать какую-нибудь из таких систем на практике, не входит в круг принципиальных вопросов, которые мы здесь рассматриваем.
Аналоговые вычисления
До сих пор я рассматривал «вычисление» только в том смысле, в котором этот термин применим к современным цифровым компьютерам или, точнее, к их теоретическим предшественникам — машинам Тьюринга. Существуют и другие разновидности вычислительных устройств, особенно широко распространенные в не столь отдаленном прошлом; вычислительные операции здесь осуществляются не посредством переходов между дискретными состояниями «вкл./выкл.», знакомыми нам по цифровым вычислениям, а с помощью непрерывного изменения того или иного физического параметра. Самым известным из таких устройств является логарифмическая линейка, изменяемым физическим параметром которой является линейное расстояние (между фиксированными точками на линейке). Это расстояние служит для представления логарифмов чисел, которые нужно перемножить или разделить. Существует много различных разновидностей аналоговых вычислительных устройств, в которых могут применяться и другие типы физических параметров — такие, например, как время, масса или электрический потенциал.
В случае аналоговых систем необходимо учитывать одно формальное обстоятельство: стандартные понятия вычисления и вычислимости применимы, строго говоря, только к дискретным системам (над которыми, собственно, и выполняются «цифровые» действия), но не к непрерывным, таким, например, как расстояния или электрические потенциалы, с которыми имеет дело традиционная классическая физика. Иными словами, для того чтобы применить обычные вычислительные понятия к системе, описание которой требует не дискретных (или «цифровых»), а непрерывных параметров, мы естественным образом должны прибегнуть к аппроксимации. Действительно, при компьютерном моделировании физических систем вообще стандартной процедурой является аппроксимация всех рассматриваемых непрерывных параметров в дискретной форме. Подобная процедура, однако, неминуемо вносит некоторую погрешность, величина которой определяется заданной степенью точности аппроксимации; при этом вполне возможно, что для той или иной интересующей нас физической системы заданной точности может оказаться недостаточно. В итоге дискретное компьютерное моделирование очень просто может привести нас к ошибочным выводам относительно поведения моделируемой непрерывной физической системы.
В принципе, ничто не мешает повысить точность до уровня, адекватного для моделирования рассматриваемой непрерывной системы. Однако на практике, особенно в случае хаотических систем, требуемые для этого время вычислений и объем памяти могут оказаться непомерно большими. Кроме того, можем ли мы, строго говоря, быть абсолютно уверенными в том, что выбранная нами степень точности является действительно достаточной. Необходим какой-то критерий, который позволил бы нам определить, что нужный уровень точности достигнут, дальнейшего ее повышения не требуется и качественному поведению, вычисленному с такой точностью, в самом деле можно доверять. Все это поднимает ряд достаточно щекотливых математических вопросов, рассматривать которые подробно на этих страницах мне представляется не совсем уместным.
Существуют, однако, и другие подходы к проблемам вычислений в случае непрерывных систем; например, такие, в которых непрерывные системы рассматриваются как самостоятельные математические структуры со своим собственным понятием «вычислимости» — понятием, обобщающим идею вычислимости по Тьюрингу с дискретных величин на непрерывные. При таком подходе исчезает необходимость в аппроксимации непрерывной системы дискретными параметрами с целью применить к ней традиционную концепцию вычислимости по Тьюрингу. Такие идеи вызывают определенный интерес с математической точки зрения; к сожалению, им, как нам представляется, не достает пока той неотразимой естественности и уникальности, которые присущи стандартному понятию вычислимости по Тьюрингу для дискретных систем. Более того, вследствие определенной непоследовательности данного подхода, формально «невычислимыми» оказываются и некоторые простые системы, в применении к которым подобная терминология выглядит как-то не совсем уместно (даже такие, например, как известное всем из физики простое «волновое уравнение»; см. [313] и НРК, с. 187-188). С другой стороны, следует упомянуть и об одной сравнительно недавней работе ([327]), в которой показано, что теоретические аналоговые компьютеры, объединяемые в некоторый достаточно обширный класс, не могут выйти за рамки обычной вычислимости по Тьюрингу. Я надеюсь, что дальнейшие исследования должным образом осветят эти безусловно интересные и важные темы. Пока же у меня нет оснований полагать, что работы в этом направлении в целом уже достигли той стадии завершенности, чтобы их результаты можно было применить к рассматриваемым здесь проблемам.
В этой книге меня в особенности занимает вопрос о вычислительной природе умственной деятельности, где термин «вычислительный» следует рассматривать в стандартном смысле вычислимости по Тьюрингу. В самом деле, компьютеры, которыми мы сегодня повседневно пользуемся, являются цифровыми, и именно это их свойство оказывается существенным для современных разработок в области ИИ. Наверное, логичным будет предположить, что в будущем может появиться «компьютер» какого-то иного типа, решающую роль в функционировании которого будут играть (пусть даже и не выходя при этом за общепринятые теоретические рамки современной физики) непрерывные физические параметры, что позволит такому компьютеру демонстрировать поведение, существенно отличное от поведения цифрового компьютера.
Как бы то ни было, все эти вопросы важны, главным образом, для проведения границы между «сильной» и «слабой» версиями позиции . Согласно слабой версии
, поведение обладающего сознанием человеческого мозга обусловлено некоторой физической активностью, которую невозможно вычислить в стандартном смысле дискретной вычислимости по Тьюрингу, но которую можно полностью объяснить в рамках современных физических теорий. Если так, то эта активность, по всей видимости, должна зависеть от каких-то непрерывных физических параметров таким образом, чтобы ее невозможно было адекватно воспроизвести с помощью стандартных цифровых процедур. В соответствии же с сильной версией
, невычислимость сознательной деятельности мозга может быть исчерпывающе объяснена в рамках некоторой невычислительной физической теории (пока еще не открытой), следствия из которой, собственно, и обусловливают упомянутую деятельность. Хотя второй вариант может показаться несколько надуманным, альтернатива (для сторонников
) и в самом деле состоит в отыскании для какого-либо непрерывного процесса в рамках известных физических законов такой роли, которую невозможно было бы адекватно воспроизвести посредством каких угодно вычислений. На данный же момент, несомненно, следует ожидать, что для любой достоверной аналоговой системы любого типа из тех, что получили более или менее серьезное рассмотрение, обязательно окажется возможным (по крайней мере, в принципе) создать эффективную цифровую модель.
Даже если не принимать во внимание всевозможные теоретические проблемы общего плана, на сегодняшний день наибольшее превосходство перед аналоговыми вычислительными системами демонстрируют именно цифровые компьютеры. Цифровые вычисления имеют гораздо более высокую точность благодаря, в основном, тому, что при хранении данных в цифровом виде повышение точности обеспечивается простым увеличением разрядности чисел, что легко достижимо с помощью весьма скромного увеличения (логарифмического) мощности компьютера; в аналоговых же машинах (по крайней мере, в полностью аналоговых, в конструкцию которых не заложено никаких цифровых концепций) увеличения точности можно добиться лишь посредством весьма и весьма значительного увеличения (линейного) соответствующих параметров. Возможно, когда-нибудь в будущем возникнут новые идеи, которые пойдут на пользу аналоговым вычислителям, однако в рамках современной технологии большая часть существенных практических преимуществ принадлежит, по всей видимости, цифровому вычислению.
Невычислительные процессы
Из всех типов вполне определенных процессов, что приходят в голову, большая часть относится, соответственно, к категории феноменов, называемых мною «вычислительными» (имеются в виду, конечно же, «цифровые вычисления»). Возможно, читатель уже начал волноваться, что сторонники позиции так и останутся у нас не при деле. Причем я еще ни словом не упоминал о строго случайных процессах, которые могут быть обусловлены, скажем, какими-либо исходными данными, получаемыми от квантовой системы. (О квантовой механике мы немного подробнее поговорим во второй части, главы 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, только что рассмотренные мною весьма специфические модели не совсем отвечают реальным требованиям точки зре-
ния . Что же касается тех феноменов, которые отвечают-таки этим самым реальным требованиям, и некоторых связанных с упомянутыми феноменами поразительных физических возможностях, то о них мы поговорим в
Завтрашний день
Так какого же будущего для этой планеты нам следует ожидать согласно точкам зрения . Если верить
то настанет время, когда соответствующим образом запрограммированные суперкомпьютеры догонят — а затем и перегонят человека во всех его интеллектуальных достижениях. Конечно же, сторонники
придерживаются различных взглядов относительно необходимого для этого времени. Некоторые вполне разумно полагают, что пройдет еще много столетий, прежде чем компьютеры достигнут уровня человека, принимая во внимание крайнюю скудость современного понимания реально выполняемых мозгом вычислений (так они говорят), обусловливающих ту тонкость поведения, какую, несомненно, демонстрирует человек, — тонкость, без которой, конечно же, нельзя говорить о каком бы то ни было «пробуждении сознания». Другие утверждают, что времени понадобится значительно меньше. В частности, Ханс Моравек в своей книге «Дети разума» [266] приводит вполне аргументированное доказательство (основанное на непрерывно ускоряющемся развитии компьютерных технологий за последние пятьдесят лет и на своей оценке той доли от всего объема функциональной активности мозга, которая на сегодняшний день уже успешно моделируется численными методами) в поддержку своего утверждения, будто уровень «эквивалентности человеку» будет преодолен уже к 2030 году. (Кое-кто утверждает, что это время будет еще короче), а кто-то даже уверен, что предсказанная дата достижения эквивалентности человеку уже осталась в прошлом!) Однако чтобы читатель не очень пугался того, что менее чем через сорок (или около того) лет компьютеры во всем его превзойдут, горькая пилюля подслащена одной радужной надеждой (подаваемой под видом гарантированного обещания): все мы сможем тогда перенести свои «ментальные программы» в сверкающие металлические (или пластиковые) корпуса роботов (конкретную модель, разумеется, каждый выберет себе сам), чем и обеспечим себе что-то вроде бессмертия [266, 267].
А вот сторонники точки зрения подобным оптимизмом похвастаться не могут. Они вполне согласны с приверженцами А относительно перспектив развития интеллектуальных способностей компьютеров — с той лишь оговоркой, что речь при этом идет исключительно о внешних проявлениях этих самых способностей. Для управления роботом необходимо и достаточно располагать адекватной моделью деятельности человеческого мозга, больше ничего не требуется (рис. 1.5). Согласно
, вопрос о том, способно ли подобное моделирование вызвать осмысленное осознание, не имеет никакого отношения к реальному поведению робота. На достижение необходимого для такого моделирования технологического уровня может уйти как несколько веков, так и менее сорока лет. Однако, как уверяют сторонники
, рано или поздно, а это все-таки произойдет. Тогда же компьютеры достигнут уровня «эквивалентности человеку», а затем, как можно ожидать, и уверенно превзойдут его, оставив без внимания все потуги нашего относительно слабого мозга хоть немного этот уровень приподнять. Причем возможности «подключения» к управляемым роботам у нас в этом случае не будет, и, похоже, придется
примириться с тем, что нашей планетой, в конечном итоге, будут править абсолютно бесчувственные машины! Мне представляется, что из всех точек зрения именно
предлагает самый пессимистичный взгляд на будущее нашей планеты — вопреки, казалось бы, тому факту, что именно она лучше всего соотносится с так называемым «здравым смыслом».
Если же верить то можно ожидать, что компьютеры навсегда сохранят подчиненное по отношению к человеку положение — какими бы быстрыми, мощными или алгоритмически совершенными они ни стали. При этом точка зрения
не отрицает возможности будущих научных разработок, которые могут привести к созданию неких устройств, принцип действия которых не будет иметь ничего общего с компьютерами в их сегодняшнем понимании, а будет основан на той самой невычислимой физической активности, которая, согласно
, обусловливает наше собственное сознательное мышление, — устройств, которые окажутся способны вместить в себя реальные разум и сознание. Быть может, в конечном итоге именно такие устройства, а вовсе не те машины, которые мы называем «компьютерами»,
и превзойдут человека в интеллектуальном отношении. Что ж, не исключено; однако подобные умозрительные прогнозы представляются мне в настоящий момент крайне преждевременными, поскольку мы практически не обладаем необходимыми для таких исследований научными познаниями, не говоря уже о каких бы то ни было технологических решениях. К этому вопросу мы еще вернемся во второй части книги