Алгоритмическая вероятность

Рэй Соломонофф первоначально определил алгоритмическую информацию в процессе поиска формальной математической теории бритвы Оккама. Средневекового философа Уильяма Оккама интересовала возможность найти самое простое объяснение наблюдаемых явлений. «Pluralitas non est ponenda sin necessitate», – объявил он («Не следует множить сущности без необходимости»). Оккам призывал искать и принимать простые объяснения явлений, отклоняя сложные. Он, безусловно, посмеялся бы над теми, кто пытался объяснить наличие регулярных линий на поверхности Марса существованием марсиан. Эти линии можно было объяснить геологическими разломами или оптической иллюзией, что не требует присутствия марсиан. Привлекать марсиан для того, чтобы объяснить линии на Марсе, это и есть «умножение сущности без необходимости», или, проще говоря, попытка сделать вещи сложнее, чем они есть. Бритва Оккама «отрезает» сложные объяснения, указывая, что простые априорно более вероятны.

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

Но в какой степени она лучше других? В 1970-х гг. Грегори Хайтин и его коллега Чарльз Беннетт из IBM рассмотрели алгоритмическую информацию с точки зрения печатающих обезьян. Предположим, обезьяна набирает на клавиатуре случайные строки битов и вводит их в компьютер. Компьютер интерпретирует эти строки как программы, написанные на подходящем языке, скажем на Java. Какова вероятность того, что компьютер выдаст первый миллион цифр числа p? Такая же, как и вероятность того, что случайные строки, введенные в компьютер обезьяной, воспроизведут программу на Java, позволяющую вычислить первый миллион цифр числа p. Вероятность того, что обезьяна правильно напечатает первый бит такой программы, разумеется, составляет 0,5, или 1/2. Вероятность того, что она правильно напечатает два первых бита, составляет 0,25, или 1/4. Вероятность того, что правильно будут напечатаны первые 1000 битов, есть 1/2, умноженная на себя 1000 раз, или 1/21000. Это очень малое число. Очевидно, чем длиннее программа, тем менее вероятно, что обезьяна правильно введет ее в компьютер.

Вероятность того, что случайная программа, которую обезьяна вводит в компьютер, выдаст первый миллион цифр числа p, называют «алгоритмической вероятностью» числа p. Поскольку вероятность случайно правильно набрать длинную программу многократно меньше, чем вероятность правильно набрать короткую, алгоритмическая вероятность максимальна для самых коротких программ. Самая короткая программа, которая может дать на выходе то или иное число, является самым вероятным объяснением того, как это число было создано.

Если взглянуть на это под другим углом, то числа, создаваемые короткими программами, с большей вероятностью окажутся выходом обезьяньего компьютера, чем числа, которые могут быть произведены лишь с помощью длинных программ. При этом множество красивых и сложных математических образов – правильные геометрические формы, фракталы, законы квантовой механики, элементарные частицы, законы химии – можно задать с помощью коротких компьютерных программ. Хотите верьте, хотите нет, но у обезьяны есть хороший шанс создать все, что мы видим вокруг!

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

Что нужно делать, чтобы это объяснение было проверяемым?[55]Чтобы вычислительное объяснение сложности работало, нужны два ингредиента: компьютер и обезьяны. Компьютер существует благодаря законам квантовой механики. Но где обезьяны? Какой физический механизм вводит информацию в нашу Вселенную, программируя ее с помощью строки случайных битов? Здесь нам тоже не нужно искать что-либо, кроме законов квантовой механики, которые постоянно вбрасывают новую информацию во Вселенную в виде квантовых флуктуаций. В ранней Вселенной, например, галактики формировались вокруг «зародышей» – мест, где плотность материи была чуточку выше, чем в других местах. Эти «зародыши» галактик возникли в результате квантовых флуктуаций: средняя плотность материи повсюду была одинаковой, но квантовая механика добавила случайные флуктуации, благодаря которым и начали формироваться галактики.

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

Случайность возникает в вычислительной Вселенной из-за того, что начальное состояние Вселенной – это суперпозиция различных состояний программы, каждое из которых отправляет Вселенную по тому или иному пути вычислений, причем некоторые из этих путей приводят к сложному и интересному поведению. Квантово-вычислительная Вселенная следует всеми этими путями одновременно, квантово-параллельно, и эти пути соответствуют декогерентным историям, описанным выше. Так как истории вычислений декогерентны, мы можем обсуждать их за обедом; лишь одна (или другая) из этих историй произошла на самом деле. Одна из этих декогерентных историй соответствует Вселенной, которую мы видим вокруг.

Дата добавления: 2015-11-14