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

Числа, которые могут быть созданы короткими программами, – это математически регулярные, правильные числа. p – одно из таких чисел, но таким является, например, и число из миллиарда единиц, которое может выдать программа, которая – в переводе на обычный язык – говорит: «Печатать 1 один миллиард раз». Но, как мы уже сказали, большинство чисел не обладают существенной математической регулярностью. Большинство чисел, по существу, являются случайными.

Самая короткая компьютерная программа, создающая число, всегда определяется для данного компьютерного языка – Java, C, Fortran, BASIC. Но ее длина не слишком сильно зависит от того, какой именно язык использован. Большинство языков могут выдать первый миллион цифр числа p с помощью всего нескольких сотен инструкций. Более того, такую программу, написанную на фортране, можно превратить в программу, написанную на Java и создающую те же самые числа, с помощью специальной программы-переводчика. Но тогда самая короткая программа на Java, позволяющая создать первый миллион цифр числа p, не будет длиннее, чем самая короткая программа на фортране плюс длина программы преобразования. Если задавать все более длинные числа, длина программы преобразования будет все меньше и меньше по сравнению с основной программой, добавляя сравнительно небольшую длину к алгоритмическому информационному содержанию.

Такая «переводимость» компьютерных программ – главная черта вычислений. Программу, написанную на Fortran, всегда можно преобразовать в другую программу, написанную на Java. Эта «переводимость» – аспект универсального характера вычислений. Еще один знакомый нам универсальный аспект вычислений состоит в том, что одни и те же программы, например Microsoft Word, могут работать на компьютерах разной архитектуры. У PC и Mac очень разные схемы коммутации, как и способ представления и исполнения инструкций. Но Word может работать на компьютерах обоих типов. Если нам нужно установить Word на Mac, эта программа транслируется (или компилируется) в ряд инструкций, которые понимает Mac, и то же самое верно для PC. Несмотря на эти различия в основе, создавая документ в Word на Mac, мы используем те же самые клавиши, чтобы составить такой же документ, как и на PC {14}.

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

Многие строки битов в реальном мире обладают математической регулярностью, поэтому их можно представить в сжатом виде. Например, в английском языке разные буквы встречаются с разной частотой: чаще всего используется буква E, за ней идут T, A, I, O, N, S, H, R, D, L, U (в эпоху типографского набора они находились в верхнем, самом доступном ряду ячеек со шрифтом) [39]. Программа, которая кодирует английский текст таким образом, что E соответствует более короткому коду, а Q – более длинному коду, может сжать текст на английском языке почти в два раза [40].

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

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