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

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

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

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

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

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

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

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

Числа, которые могут быть созданы короткими программами, – это математически регулярные, правильные числа. 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].

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