Дэвид Дойч - Структура реальности. Наука параллельных вселенных
Я уже говорил о важности универсальности вычислений – о том, что один физически возможный компьютер может, при наличии достаточного времени и памяти, выполнить любое вычисление, доступное любому другому физически возможному компьютеру. Законы физики, как мы их сейчас понимаем, признают универсальность вычислений. Но для того, чтобы универсальность была полезной или важной в общей схеме вещей, сказанного мною недостаточно. Приведенное определение просто означает, что в конечном итоге универсальный компьютер сможет сделать то, что может сделать любой другой компьютер. Другими словами, он универсален при наличии достаточного времени. А что делать, если времени недостаточно? Представьте себе универсальный компьютер, который мог бы выполнить только одно вычислительное действие за всю жизнь Вселенной. Его универсальность по-прежнему оставалась бы глубоким свойством реальности? Вероятно, нет. Обобщая, можно раскритиковать такое узкое понятие универсальности, поскольку оно признает задачу входящей в репертуар компьютера без учета физических ресурсов, которые придется израсходовать компьютеру на выполнение этой задачи. Так, например, мы рассматривали пользователя виртуальной реальности, готового к остановке мозга на миллиарды лет, пока компьютер вычисляет, какую анимацию показывать дальше. Такое отношение вполне уместно при обсуждении пределов виртуальной реальности. Но когда мы говорим о ее полезности, или, что даже более важно, фундаментальной роли, которую она играет в структуре реальности, нам следует быть более разборчивыми. Эволюция никогда бы не произошла, если бы задача воспроизведения определенных свойств самых первых, простейших сред обитания не была легкорешаемой (т. е. вычислимой в течение разумного периода времени) при использовании в качестве компьютеров легкодоступных молекул. Точно так же никогда не началось бы развитие науки и техники, если бы для изобретения каменного инструмента понадобились тысячи лет размышлений. Более того, то, что было истиной в самом начале, остается абсолютным условием прогресса на каждом этапе. Универсальность вычислений была бы бесполезна для генов независимо от количества содержащегося в них знания, если бы воссоздание организма не было легкорешаемой задачей – скажем, если бы один репродуктивный цикл занимал миллиарды лет.
Таким образом, факт существования сложных организмов и непрерывного ряда постепенно совершенствующихся изобретений и научных теорий (таких как механика Галилея, механика Ньютона, механика Эйнштейна, квантовая механика) говорит кое-что еще о том, какого рода универсальность вычислений существует в реальности. Он говорит нам, что действительные законы физики, по крайней мере, до сих пор, поддаются последовательной аппроксимации с помощью теорий, дающих все лучшие объяснения и предсказания, и что задача открытия каждой теории при наличии предыдущей является вычислительно разрешимой на базе ранее открытых законов и ранее созданных технологий. Структура реальности должна быть (и была) многоуровневой для легкого доступа к самой себе. Подобным образом, если рассматривать саму эволюцию как вычисление, этот факт говорит нам, что существовало достаточно много жизнеспособных организмов, закодированных с помощью ДНК, что позволило организмам с более высокой степенью адаптации быть вычисленными (т. е. проэволюционировать), используя ресурсы, предоставленные их предками с меньшей степенью адаптации. Таким образом, мы можем сделать вывод, что законы физики не только предписывают свою собственную постижимость через принцип Тьюринга, но и гарантируют, что соответствующие эволюционные процессы, такие как жизнь и мышление, не являются слишком затратными по времени и требуют не слишком много ресурсов иного рода, чтобы произойти в реальности.
Итак, законы физики не только позволяют (или, как я обосновал, требуют) существование жизни и мышления, но требуют от них эффективности, в некотором определенном смысле. Для выражения этого чрезвычайно важного свойства реальности современный анализ универсальности обычно исходит из возможности существования компьютеров, универсальных даже в более строгом смысле, чем того требует сам принцип Тьюринга: универсальные генераторы виртуальной реальности не только возможны, но их можно построить так, что они не потребуют непрактично больших ресурсов для воспроизведения простых аспектов реальности. В дальнейшем, говоря об универсальности, я буду иметь в виду именно такую универсальность, если не сказано иного.
Насколько эффективно можно воспроизвести те или иные аспекты реальности? Другими словами, какие вычисления можно практически выполнить за данное время и при данных возможностях? Это основной вопрос теории вычислительной сложности, которая, как я уже сказал, занимается изучением ресурсов, необходимых для решения вычислительных задач. Теория сложности еще не объединена в достаточной степени с физикой, чтобы дать многие ответы в количественном виде. Однако она достигла немалого успеха в важном деле грубого различия вычислительных задач на легко- и труднорешаемые. Общий подход лучше всего проиллюстрировать на примере. Рассмотрим задачу умножения двух достаточно больших чисел, скажем, 4 220 851 и 2 594 209. Многие из нас помнят тот метод умножения, которому мы научились в детстве. Он включает умножение каждой цифры одного числа поочередно на каждую цифру другого, сдвиг промежуточных результатов и их сложение. Этот стандартный алгоритм позволяет получить окончательный ответ, в данном случае – 10 949 769 651 859. Вероятно, многие не захотят признать, что эта утомительная процедура делает умножение «легкой» задачей хоть в каком-то обыденном смысле этого слова. (В действительности существуют более эффективные методы умножения больших чисел, но этот весьма нагляден.) Однако с точки зрения теории сложности, которая имеет дело с трудными задачами, решаемыми компьютерами, не подверженными скуке и почти никогда не ошибающимися, этот метод определенно попадает в категорию «легких».
В соответствии со стандартным определением для «легкости» решения задачи важно не фактическое время, затрачиваемое на умножение конкретной пары чисел, а тот факт, что при применении того же самого метода даже к большим числам время увеличивается не слишком резко. Возможно, это покажется неожиданным, но такой очень косвенный метод определения «легкости» очень хорошо работает на практике для многих (хотя и не всех) важных классов вычислительных задач. В случае умножения, например, нетрудно убедиться, что стандартный метод можно использовать и для умножения чисел, скажем, в десять раз больших, приложив совсем незначительные дополнительные усилия. Ради иллюстрации предположим, что каждое элементарное умножение одной цифры на другую занимает у некоторого компьютера одну микросекунду (включая время, необходимое для сложения, сдвига и других операций, сопровождающих каждое элементарное умножение). При умножении семизначных чисел 4 220 851 и 2 594 209 каждую из семи цифр первого числа нужно умножить на каждую из семи цифр второго числа. Таким образом, общее время, необходимое для умножения (если операции выполняются последовательно), составит семью семь, или 49 микросекунд. Если на вход поданы числа примерно в десять раз бо́льшие, то есть содержащие по восемь цифр, на их умножения потребуется 64 микросекунды: увеличение составляет всего 31 %.
Ясно, что числа из огромного диапазона – безусловно содержащего любые числа, которые когда-либо были измерены как количественные значения физических переменных, – можно перемножить за крошечную долю секунды. Таким образом, умножение действительно является легкорешаемой задачей для любых целей в пределах физики (или, по крайней мере, в пределах существующей физики). За пределами физики, конечно, могут появиться практические причины для умножения куда больших чисел. Например, для криптографии огромный интерес представляют произведения простых чисел, состоящих примерно из 125 цифр. Наша гипотетическая машина могла бы перемножить два таких простых числа, получив произведение, состоящее из 250 цифр, примерно за 0,01 секунды. За одну секунду она могла бы перемножить два тысячезначных числа, и современные компьютеры легко могут улучшить это достижение. Лишь немногие исследователи эзотерических областей чистой математики интересуются перемножением столь непостижимо больших чисел, однако мы видим, что даже у них нет причины считать умножение неразрешимой задачей.
Напротив, разложение на множители – по сути, процесс, обратный умножению, – кажется гораздо сложнее. Вначале вводится одно число, скажем, 10 949 769 651 859. Задача заключается в том, чтобы найти два его множителя – меньших числа, произведение которых равно 10 949 769 651 859. Поскольку мы только что перемножили эти числа, мы знаем, что в данном случае ответ будет 4 220 851 и 2 594 209 (и поскольку оба эти числа простые, это единственный подходящий ответ). Но не располагая заранее такой подсказкой, как бы мы нашли эти множители? Если в поисках простого метода вы обратитесь к детским воспоминаниям, то это будет бесполезно, поскольку такого метода не существует.
