Книга: Новый ум короля: О компьютерах, мышлении и законах физики

Вычислима ли жизнь в бильярдном мире?

Вычислима ли жизнь в бильярдном мире?

Позвольте мне сначала показать на умышленно абсурдном искусственном примере, что вычислимость и детерминизм — понятия различные. Для этого я продемонстрирую «игрушечную модель вселенной», которая детерминистична, но не вычислима. Пусть «состояние» этой вселенной в любой «момент времени» описывается как пара натуральных чисел (m, n). Пусть Т_u — фиксированная универсальная машина Тьюринга, например, та, которая описана в главе 2 («Универсальная машина Тьюринга»). Чтобы решить, какое состояние этой вселенной наступит в следующий «момент времени», нам необходимо спросить, остановится ли действие машины Тьюринга Т_u на m или не остановится (в обозначениях главы 2, «Неразрешимость проблемы Гилберта» Т_u(m) ? ? или Т_и(m) = ?). Если машина Тьюринга Т_и останавливается, то состояние в следующий момент времени есть (m + 1, n). Если же машина Тьюринга не останавливается, то состояние в следующий момент времени должно быть (n+1, m). В главе 2 было показано, что не существует алгоритма для решения проблемы остановки машины Тьюринга. Следовательно, не может быть алгоритма предсказания «будущего» в рассматриваемой модели вселенной, несмотря на то, что эта модель вполне детерминистична[110].

Разумеется, описанную выше модель не следует принимать всерьез, но она показывает, что вопрос все же существует и на него необходимо найти ответ. Относительно любой детерминистской физической теории мы сможем спросить, вычислима она или нет. Действительно, вычислим ли ньютонианский бильярдный мир?

Вопрос о физической вычислимости отчасти зависит от того, какого рода информацию о данной системе мы хотим получить. Я могу придумать целый ряд вопросов о конкретной физической системе, на которые — как мне кажется — в случае ньютоновской бильярдной модели не существует вычислимого (т. е. алгоритмически получаемого) ответа. Одним из таких вопросов мог бы быть следующий: столкнется ли когда-нибудь шарик А с шариком В? Имеется в виду, что в качестве начальных условий нам в некоторый момент времени (t = 0) задаются положения и скорости всех шариков; и задача состоит в том, чтобы, исходя из этих данных, выяснить, сталкиваются или не сталкиваются шарики А и В в некоторый последующий момент времени (t > 0). Чтобы придать задаче бо?льшую конкретность (хотя и сделав ее при этом не особенно реалистичной), мы можем предположить, что все шарики имеют одинаковый радиус и одинаковую массу и что, скажем, сила, действующая между шариками, обратно пропорциональна квадрату расстояния между ними. Одна из причин, по которой я сделал предположение о невозможности алгоритмически получить ответ на этот вопрос, заключается в том, что сама модель несколько напоминает «бильярдную модель для вычисления», предложенную Эдвардом Фредкином и Томмазо Тоффоли (Фредкин, Тоффоли [1982]). В их модели шарики (вместо того, чтобы попарно взаимодействовать по закону обратных квадратов) были ограничены различными «стенками», но упруго отражались при столкновениях друг с другом — по аналогии с теми ньютоновскими шариками, которые я только что описывал (рис. 5.9).

В модели Фредкина — Тоффоли все основные логические операции компьютера могут выполняться с помощью шариков. Модель позволяет имитировать вычисления, производимые любой машиной Тьюринга: конкретный выбор машины Тьюринга Т_u определяет конфигурацию «стенок» и т. д. в машине Фредкина — Тоффоли; начальное состояние движущихся шариков соответствует информации на входной ленте машины Тьюринга; а содержимое на выходной ленте соответствует конечному состоянию шариков. Таким образом, можно, в частности, спросить: останавливается ли когда-нибудь такая-то и такая-то машина Тьюринга? «Остановка» может быть сформулирована как состояние при котором шарик А сталкивается, в конце концов, с шариком В. То, что на этот вопрос невозможно ответить алгоритмически (см. гл.2 «Неразрешимость проблемы Гильберта»), по крайней мере наводит на мысль о том, что ньютоновский вопрос «сталкивается ли когда-нибудь шарик А с шариком В?», который был поставлен мной первоначально, тоже не может быть разрешен алгоритмически.

В действительности, ньютоновская задача является гораздо более каверзной, чем задача, поставленная Фредкином и Тоффоли. Эти авторы могли задавать состояние своей модели с помощью дискретных параметров (т. е. при помощи утверждений «да или нет» типа «шарик либо находится в данном туннеле, либо не находится»). Но в полной ньютоновской задаче начальные положения и скорости шариков необходимо задавать с бесконечной точностью в терминах координат, которые являются действительными числами, а не принимают дискретные значения. Таким образом, мы снова сталкиваемся со всеми проблемами, которые нам уже приходилось рассматривать, когда в главе 4 мы пытались ответить на вопрос, рекурсивно ли множество Мандельброта. Что означает «вычислимость», когда в качестве входных и выходных данных допускаются непрерывно изменяющиеся параметры?[111] Проблему можно слегка облегчить, предположив, что все начальные положения и скорости заданы рациональными числами (хотя нельзя ожидать, что координаты и компоненты скорости останутся рациональными в более поздние рациональные моменты времени t). Напомним, что рациональное число представимо в виде отношения двух целых чисел и, следовательно, определяется в дискретных конечных терминах. Используя рациональные числа, мы можем сколь угодно точно аппроксимировать любые наборы начальных данных, которые собираемся использовать в своих вычислениях. И предположение о том, что при рациональных начальных данных может не существовать алгоритма, позволяющего определить, столкнутся в конце концов или нет шарики А и В, — отнюдь не лишено смысла.

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

Чтобы окончательно удостовериться в том, что шарик А действительно никогда не сталкивается с шариком В, пришлось бы прождать вечность! Разумеется, машины Тьюринга ведут себя именно так.

На самом деле, существуют, по-видимому, достаточно весомые указания в пользу своего рода вычислимости ньютонианского бильярдного мира (по крайней мере, если оставить в стороне проблему множественных столкновений). Способ, которым мы пользуемся для того, чтобы рассчитать поведение такого мира, сводится к введению аппроксимаций. Мы могли бы предположить, что центры шариков по определению располагаются в узлах некоторой точечной решетки, причем координаты узлов измерены, например, с точностью до сотых долей единицы. Время также можно считать «дискретным»: все допустимые моменты времени должны быть кратными некоторой небольшой единице (обозначаемой, скажем, ?t). Это приводит к разным дискретным возможностям для «скоростей» (разностей между значениями положений точек на решетке В два последовательных разрешенных момента времени, деленных на ?t). Соответствующие приближения для. ускорений вычисляются с использованием закона силы, и, в свою очередь, используются для получения значений «скоростей». После чего с требуемой точностью вычисляются новые положения шариков в узлах решетки в следующий допустимый момент времени. Вычисления производятся до тех пор, пока сохраняется указанная точность. Вполне может оказаться, что точность будет потеряна раньше, чем мы успеем рассчитать состояние системы для достаточно большого числа моментов времени. В этом случае процедура начинается снова со значительно более мелкой пространственной решеткой и более частыми допустимыми моментами времени. Это позволяет достичь большей точности — и рассчитать поведение системы в более отдаленном будущем. Такой прием дает возможность математически описывать ньютоновский бильярдный мир (игнорируя множественные столкновения) сколь угодно точно, и в этом смысле можно сказать, что ньютонианский мир действительно вычислим.

Но в то же время можно сказать и обратное: что в некотором (практическом) смысле этот мир «невычислим», поскольку точность, с которой могут быть известны начальные данные, всегда ограничена. Действительно, такого рода задачам всегда присуща некоторая (и весьма значительная) «нестабильность». Очень небольшое изменение в начальных условиях может привести к возникновению чудовищных изменений в конечном состоянии. (Всякий, кто пытался загнать в лузу бильярдный шар, стремясь ударить его промежуточным шаром, поймет, что я имею в виду!) Сказанное становится очевидным, когда происходят (последовательные) столкновения, но такие неустойчивости в поведении могут встречаться и в случае действия ньютоновского тяготения на расстоянии (если гравитирующих тел больше двух). Для обозначения этого типа неустойчивости часто используется термин «хаос», или «хаотическое поведение». Например, хаотическое поведение важно, когда речь заходит о погоде. Хотя ньютоновские уравнения, управляющие стихиями, хорошо изучены, долговременный прогноз погоды печально известен своей ненадежностью!

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

Обсуждая в общем и целом вопросы вычислимости и непредсказуемости, нам будет полезно принять более широкую, чем прежде, точку зрения на природу физических законов. Это позволит рассматривать не только схему ньютоновской механики, но и более поздние теории, пришедшие ей на смену. И сперва нам стоит окинуть беглым взглядом замечательную формулировку законов механики, предложенную Гамильтоном.

Оглавление книги