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

Обезьяны, печатающие текст на пишущих машинках (рис. 15a), выдают бессмыслицу. Если же обезьяны будут вводить текст в компьютеры (рис. 15b), то компьютер интерпретирует эту бессмыслицу как компьютерную программу и начнет создавать сложные структуры

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

Алгоритмическая информация

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

Во второй главе мы видели, что компьютерные языки позволяют придавать строкам битов тот или иной смысл. На таком языке эти строки можно интерпретировать как инструкции, побуждающие компьютер создавать те или иные выходные данные. Однако для любого желаемого выхода есть множество возможных языков, и, как правило, желаемый результат могут выдать многие компьютерные программы. Например, существует много разных программ, которые на выходе дают первый миллион цифр числа p. Важно отметить, однако, что не все эти программы одинаковой длины. Одна программа просто говорит: «Напечатать 3,1415926…» (где «…» состоит из остальных 999 992 цифр). Эта программа очень простая, но длинная. Более короткая, хотя и более сложная программа будет описывать конкретный способ для вычисления этого миллиона цифр. Например, такая программа может следовать примеру древних греков и аппроксимировать окружность в виде последовательности сторон многоугольника все меньшей длины. Такая программа для вычисления числа p может состоять всего из нескольких сотен инструкций.

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

Алгоритмическое информационное содержание независимо друг от друга открыли в начале и середине 1960-х гг. ученый Рэй Соломонофф из Кембриджа, Массачусетс, российский математик Андрей Николаевич Колмогоров и Грегори Хайтин, которому тогда было 18 лет и который учился в Сити-колледже в Нью-Йорке. Все эти исследователи отметили, что алгоритмическое информационное содержание обеспечивает в некоторых случаях более удовлетворительное измерение информации, чем длина записи числа в битах (это еще один способ описать информационное содержание числа), потому что алгоритмическая информация учитывает присущую числу математическую регулярность, а длина в битах на это не способна.

Для большинства чисел алгоритмическое информационное содержание близко к длине числа в битах. Оно не может намного превышать длину числа, ведь любое число, например 01110110101110111011101, можно получить с помощью простейшей программы, которая говорит: «Напечатать 01110110101110111011101». Для большинства чисел алгоритмическое информационное содержание не может быть и намного короче самого числа, просто потому что коротких программ гораздо меньше, чем длинных чисел. Например, можно спросить, сколько двадцатибитных чисел могут создавать десятибитные программы. Существует 220 (то есть 1 048 576) двадцатибитных чисел, но только 1024 = 210 возможных десятибитных программ. Поэтому в самом лучшем случае десятибитные программы могут создать лишь одно из каждых 1024 двадцатибитных чисел.