, содержится в математической формуле, описывающей это число, и, следовательно, нам не нужно бесконечное количество информации.
Этот альтернативный взгляд привел к появлению алгоритмической теории информации. Эта математическая теория, которая дополняет теорию Шеннона, была разработана сначала русским математиком Андреем Колмогоровым (1903–1987), а затем — аргентинско-американским математиком Грегори Хайтином (1947). Она основывается на понятии алгоритма — набора простых инструкций для компьютера. Ниже приведен пример алгоритма на вымышленном языке программирования, с помощью которого можно определить, является число символов во фразе четным или нечетным.
1. Посчитай число символов во фразе и сохрани результат в х.
2. Вычисли остаток деления х на два и сохрани результат в r.
3. Если r равен нулю, напиши на экране: «Число символов четное».
4. Если r не равен нулю, напиши на экране: «Число символов нечетное».
* * *
ГРЕГОРИ ХАЙТИН
Грегори Хайтин, родившийся в 1947 году, — аргентинско-американский программист и математик. Еще будучи подростком, он вывел алгоритмическую теорию информации и свою собственную версию теоремы Гёделя о неполноте, где показал, что количество недоказуемых теорем в математике намного больше, чем было принято считать. Сейчас Хайтин занимается метабиологией — математическим подходом к биологии, который изучает случайное развитие компьютерных программ для понимания биологической эволюции и возникновение творчества в строгой математической форме.
* * *
Согласно алгоритмической теории информации, информация, содержащаяся в цепочке символов, задана длиной самой короткой программы, которая ее порождает. Возьмем цепочку:
Существует программа, порождающая ее с помощью очень короткого кода.
1. Напиши единицу.
2. Вернись к началу программы.
В этой цепочке содержится очень мало информации.
Важно, что количество информации зависит от используемого языка программирования. Так, программа на языке Java и программа на языке С имеют разное количество строк, даже если обе делают одно и то же. Чтобы преодолеть эту проблему, воспользуемся понятием универсального языка программирования: язык программирования универсален, если его можно использовать для написания любой программы, которую можно написать на любом другом языке. Все существующие сегодня языки программирования универсальны, в том смысле что можно создать программу на языке Java, которая понимала бы программы, написанные на
