Книга: Программируя Вселенную. Квантовый компьютер и будущее науки

Вычисления и сложность

Вычисления и сложность

Вселенная, которую мы видим за окном, удивительно сложна, она полна разнообразных форм и превращений. Тем не менее, насколько нам известно, законы физики просты. Как такие простые законы позволяют существовать таким сложным явлениям?

Чтобы ответить на этот вопрос, давайте сначала рассмотрим старые (и ошибочные) представления о том, почему Вселенная так сложна.

В последние годы XIX в. три физика – Джеймс Клерк Максвелл, Людвиг Больцман и Джозайя Уиллард Гиббс – обнаружили, что термодинамическая величина, известная как энтропия, представляет собой, как мы уже говорили, форму информации, а именно информацию, которая не известна. Вдохновленный концепцией информации, Больцман предложил оригинальное объяснение порядка и разнообразия Вселенной. Предположим, сказал Больцман, что информация, которая определяет Вселенную, является результатом абсолютно случайного процесса, как если бы значение каждого бита определялось подбрасыванием монетки.

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

Образ печатающих обезьян Бореля позже позаимствовал британский астроном и математик Артур Эддингтон – в его варианте обезьяны могли бы воспроизвести все книги Британского музея. Версию Эддингтона подхватил сэр Джеймс Джинс, который ошибочно приписал ее Томасу Гексли. В дебатах с епископом Уилберфорсом относительно «Происхождения видов» Дарвина, состоявшихся в 1860 г., Гексли действительно упоминал об обезьянах. Уилберфорс спросил тогда, произошел ли Гексли от обезьяны, и если да, то со стороны дедушки или бабушки, на что Гексли ответил, что предпочел бы произойти от обезьяны, чем от человека большого ума, который использует сей дар на службе лжи. Но ни в одном из современных отчетов об этих дебатах не упоминается об обезьянах, корпящих над пишущими машинками (которые в то время еще не были изобретены).

К середине XX в. идея об обезьянах, случайным образом воспроизводящих всю мировую литературу, проникла на страницы журнала The New Yorker в рассказе Рассела Мэлони «Несокрушимая логика». Обезьяны-машинистки начали то и дело появляться в произведениях Айзека Азимова, Дугласа Адамса и других. Типичная история о печатающих обезьянах начинается с того, что некий исследователь собирает команду обезьян и учит их печатать на машинке. Одна обезьяна вставляет в машинку чистый лист бумаги и начинает печатать: «Гамлет. Акт I, сцена 1…»

То, что какая-нибудь обезьяна напишет «Гамлета», безусловно, возможное событие. Равным образом возможно, что информация, определяющая Вселенную, появилась в столь же случайном процессе. В конце концов, если «орел» обозначить как 1, а «решку» – как 0, то, неустанно подбрасывая монету, мы в конечном итоге можем получить любую желаемую строку битов конечной длины, включая и ту, которая описывает Вселенную в целом.

Очевидное возражение против возможности создать длинный осмысленный текст в ходе абсолютно случайных процессов было высказано больше 2000 лет назад Цицероном. В его «De natura deorum» («О природе богов») стоик Луцилий Бальб представляет следующий аргумент против позиции атомистов (таких как Демокрит), утверждавших, что порядок природы проистекает из случайных столкновений атомов: «Так как же мне не удивляться человеку, убедившему себя в том, что существуют какие-то плотные и неделимые тела, которые носятся [в пространстве] под действием силы тяжести, и что от случайных столкновений между этими телами образовался прекраснейшим образом украшенный мир? Не понимаю, почему бы человеку, который считает, что так могло произойти, не поверить также, что если изготовить из золота или из какого-нибудь другого материала в огромном количестве все двадцать одну буквы, а затем бросить эти буквы на землю, то из них сразу получатся «Анналы» Энния, так что их можно будет тут же и прочитать. Вряд ли по случайности может таким образом получиться даже одна строка».

Давайте перефразируем аргумент Бальба в применении к обезьянам. Хотя Вселенная могла быть создана целиком и полностью в результате случайных бросков монетки, но это очень маловероятно, учитывая конечный возраст и размеры Вселенной. На самом деле вероятность получить столь упорядоченную Вселенную, как наша, в результате случайных бросков монетки настолько мала, что практически равна нулю. Чтобы увидеть, насколько мала эта вероятность, вернемся к метафоре об обезьянах. На стандартной клавиатуре пишущей машинки около пятидесяти клавиш. Даже если мы забудем о заглавных буквах, вероятность того, что обезьяна напечатает букву «к», составляет один к пятидесяти. Вероятность того, что обезьяна напечатает слог «ко» – одна пятидесятая пятидесятой, или 1:2500. Вероятность того, что обезьяна напечатает слово «кот», составляет одну пятидесятую пятидесятой пятидесятой, или 1:125 000. Вероятность того, что обезьяна напечатает фразу из двадцати двух букв – приблизительно 10–38. Потребовался бы миллиард миллиардов обезьян, каждая из которых печатает десять букв в секунду на протяжении примерно миллиарда миллиардов секунд существования Вселенной, для того чтобы всего одна из них напечатала слова «Гамлет. Акт I, сцена 1».

Вот практический пример: популярный веб-сайт http://everything2.com/title/Monkey+Shakespeare+Simulator может «завербовать» ваш компьютер в качестве «обезьяны» в попытке воспроизвести случайным образом отрывки из Шекспира. Рекордом на данный момент являются первые двадцать четыре буквы из второй части «Генриха IV». На то, чтобы случайно набрать их, виртуальным «машинисткам» потребовалось 2 737 850 миллионов миллиардов миллиардов миллиардов обезьяно-лет.

Сочетание очень малых вероятностей с конечным возрастом и протяженностью видимой Вселенной делает абсолютно случайное возникновение порядка крайне маловероятным. Если бы возраст или размеры Вселенной были бесконечными, то когда-нибудь или где-нибудь могли бы появиться все возможные паттерны, тексты и строки битов. Но даже в бесконечной Вселенной довод Больцмана оказывается несостоятельным. Если бы порядок, который мы видим, возник совершенно случайно, то всякий раз, когда мы получали новые биты информации, они тоже, скорее всего, были бы случайными. Но это не так: новые биты, как показывают наблюдения, редко оказываются совершенно случайными. Если вы в это не верите, просто подойдите к окну и посмотрите на улицу или возьмите яблоко и откусите от него кусочек. Любое из этих действий создаст новые, но неслучайные биты.

Вот другой пример: в астрономии в поле зрения телескопов постоянно новые галактики и другие космические структуры, например квазары{4}. Если бы доводы в пользу абсолютной случайности были справедливы, то эти новые объекты оказывались бы абсолютно случайными сгустками вещества – чем-то вроде космической слякоти, а не квазарами и упорядоченными, хотя и таинственными небесными телами, которые мы видим на самом деле.

Короче говоря, объяснение порядка по Больцману не является невозможным. Однако оно чрезвычайно маловероятно.

Просто ради удовольствия давайте посмотрим, сколько строк из «Гамлета» могло бы быть создано в ходе случайных процессов с тех пор, как возникла Вселенная. Вселенная полна фотонов – частиц света, оставшихся после Большого взрыва. Существует приблизительно 1090 фотонов, и в каждом фотоне «записано» всего несколько случайных битов. Если мы интерпретируем эти биты как буквы английского языка, то где-нибудь найдется несколько фотонов, которые можно прочесть как «Гамлет. Акт I, сцена 1. Эльсинор. Площадка перед замком».

Даже если предположить, что каждая элементарная частица – это обезьяна, печатающая с максимальной скоростью, которую позволяют законы физики, то, с тех пор как возникла Вселенная, самый длинный отрывок из «Гамлета», который можно было бы создать случайным набором текста, – это «Гамлет. Акт I, сцена I. Эльсинор. Площадка перед замком. Франсиско на страже». Увы, Бернардо не успеет даже войти и произнести свою первую реплику: «Кто здесь?»

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

Больцман ошибался: Вселенная не является совершенно случайной. Но это не значит, что Бальб Цицерона был прав. Он тоже ошибался. Для создания сложных и запутанных структур вовсе не нужны сложная и запутанная машина – или разум. Повторю еще раз: компьютеры – простые машины. Они действуют, выполняя раз за разом небольшой набор очень несложных операций. Но, несмотря на простоту компьютеров, их можно запрограммировать так, чтобы создать структуры любой желаемой сложности. Программы, создающие эти объекты, не должны сами обладать никаким очевидным порядком, они могут вообще быть случайными последовательностями битов! И рождение случайных битов действительно играет ключевую роль в создании порядка во Вселенной, только не так прямолинейно, как представлял себе Больцман.

Вселенная содержит случайные биты, происхождение которых можно проследить вплоть до квантовых флуктуаций сразу после Большого взрыва. Мы видели, как эти случайные биты могут стать «семенами» будущего разнообразия, от положения галактик до локаций мутаций в ДНК. Эти случайные биты, постулируемые квантовой механикой, в свою очередь, запрограммировали дальнейшее поведение Вселенной.

Вернемся, однако, к нашим обезьянам. На сей раз, вместо того чтобы заставлять обезьян печатать случайные последовательности букв на пишущей машинке, давайте сделаем так, чтобы они вводили эти случайные последовательности в компьютер. (Изображения обезьян, сидящих за компьютерами, можно найти повсюду, по крайней мере в киберпространстве. Впервые я услышал эту метафору от Чарльза Беннетта и Грегори Хайтина из IBM еще в 1980-х.) Например, мы усаживаем обезьяну за компьютер и говорим компьютеру, что машинописный текст – это программа на машинном языке, таком как Java. Тогда компьютер будет интерпретировать случайные знаки, введенные обезьянами, не как текст, а как компьютерную программу, то есть как последовательность инструкций определенного машинного языка[10].

Что будет, если компьютер попытается выполнить эту случайную программу? Скорее всего, он запутается и остановится, выдав сообщение об ошибке. Мусор на входе – мусор на выходе. Но иногда короткие компьютерные программы, то есть программы с относительно высокой вероятностью быть сгенерированными случайно, на самом деле могут выдавать интересный результат. Например, всего несколько строк кода могут заставить компьютер выдавать одну за другой цифры число «пи». Другая короткая программа заставит компьютер создавать сложные фракталы. Третья короткая программа заставит его моделировать Стандартную модель элементарных частиц. Еще одна программа побудит его моделировать первые моменты Большого взрыва. Еще одна позволит компьютеру моделировать химические процессы. А еще одна сделает так, что компьютер начнет доказывать все возможные математические теоремы.

Почему компьютеры создают интересные результаты, выполняя такие короткие программы? Компьютер можно назвать устройством для создания образов: любой мыслимый образ, который возможно описать на каком-то языке, может быть создан компьютером. Основное различие между обезьянами, печатающими на машинке, и обезьянами, вводящими буквы в компьютер, состоит в том, что во втором случае случайные биты, которые они создают, интерпретируются как инструкции.

Как мы показали, в текстах, которые печатает обезьяна, практически нет осмысленных структур. Когда обезьяна печатает на пишущей машинке случайные символы, машинка просто воспроизводит бессмысленные строки. Но когда обезьяна вводит строки в компьютер, компьютер интерпретирует эти бессмысленные последовательности как инструкции и использует как основу для создания образов[11].

Квантовая механика поставляет Вселенной «обезьян» в форме случайных квантовых колебаний, например тех, что стали зародышами галактик и задали их расположение. Компьютер, в который они вводят информацию, – сама Вселенная. Стартуя из простого начального состояния и подчиняясь простым законам физики, Вселенная систематически обрабатывает и усиливает биты информации, воплощенные в этих квантовых колебаниях. Результат этой обработки информации – разнообразный, пронизанный информацией мир, который мы видим вокруг: запрограммированная квантами, физика сначала создала химию, а потом жизнь; запрограммированная мутациями и рекомбинацией генов, жизнь создала Шекспира; запрограммированный опытом и воображением, Шекспир создал «Гамлета». Можно сказать, что разница между обезьяной за пишущей машинкой и обезьяной за компьютером – это единственная разница, существующая в мире.

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