Случайность и хаос - Рюэль Д.
Скачать (прямая ссылка):
сообщении, если дано семейство сообщений, к которому оно принадлежит. В
частности, если приняты все сообщения, состоящие из символов 0 и 1, то
последовательность миллиона 0 несет количество информации, равное одному
миллиону битов. Другая идея, предложенная Соломоновым, Колмогоровым и
Чайтином4, состоит в том, чтобы рассматривать длину (в битах) самой
короткой компьютерной программы, которая на выводе создаст интересующее
нас сообщение. В настоящем случае программа напоминала бы что-то вроде
"напечатать один миллион 0", и ее длина была бы гораздо короче одного
миллиона. Величину, определенную таким образом, назвали алгоритмической
информацией, или сложностью Колмогорова - Чайтина. Это сложность в том
смысле, что она измеряет, насколько трудно создать сообщение (насколько
трудно в смысле длины программы, в битах, а не в смысле времени
вычисления). В зависимости от выбранного компьютера возможны несколько
немного отличных определений, но при этом можно, например,
воспользоваться универсальной машиной Тьюринга.
Если сообщение "ля-ля-ля... " содержит миллион битов, то его К.-Ч.
(Колмогоров-Чайтин)-сложность не может намного превышать миллион, потому
что вы можете напечатать его, используя программу "напечатать "ля-ля-
ля... "". Кроме того, если сообще-
Сложность и теорема Геделя
139
ние содержит миллион битов, его К.-Ч.-сложность обычно ненамного меньше
одного миллиона. (Это имеет смысл: большинство сообщений невозможно
сжать, к примеру, до 10 процентов их первоначальной длины; это свойство
присуще лишь очень малой доле сообщений.) Это довольно простые замечания.
Но позвольте мне вернуться к более сложной задаче: дано некоторое
сообщение, требуется определить его К.-Ч.-сложность. Вы зевали, не так
ли? Вас не волнует К.-Ч.-сложность? Вам скучно? Что ж, я воспользуюсь
снижением вашей бдительности в своих целях, дам вам плохой совет... и
через несколько минут вы увязнете в логическом парадоксе и будете умолять
сжалиться над вами.
Каким образом мы определяем К.-Ч.-сложность сообщения "ля-ля-ля... "
длиной в миллион битов? Мы составляем список всех программ, длина которых
ненамного превышает один миллион битов, вставляем их одну за другой в
свой компьютер и смотрим, что получится. Длина самой короткой программы с
выводом "ля-ля-ля. .. " является К.-Ч.-сложностью этого сообщения. Ничего
нет проще. На практике это может занять слишком много времени, чтобы
считать это простым, но вы же не видите никакой причины, по которой
этого, в принципе, невозможно сделать. Или видите?
Ну что ж! Пока мы сидим за своим дружелюбным компьютером, мы можем
попросить его распечатать сообщение, которое идет первым по алфавиту
среди тех, что имеют К.-Ч.-сложность, равную, по крайней мере, одному
миллиону. Я оставляю вам задачу определения алфавитного порядка сообщений
в данном контексте. Я оставляю вам и задачу написания "суперпрограммы",
которая печатает первое сообщение (в алфавитном порядке) со сложностью,
равной, по крайней мере, миллиону. Эта суперпрограмма должна быть
достаточно короткой (она проверяет конечное число программ и
распечатывает один вывод). Если вы хоть сколько-то смыслите в
программировании, ваша суперпрограмма должна содержать менее миллиона
битов... и вот вы попались, увязли в парадоксе по самое горло, и просите
сжалиться над вами: с помощью программы, содержащей менее миллиона битов,
вы определили сообщение с К.-Ч.-сложностью, равной, по крайней мере,
одному миллиону, что противоречит определению К.-Ч.-сложности.
Что вы сделали не так? Логики скажут вам, что ваша ошибка состояла в том,
что вы сидели за компьютером после того, как ввели программу, и
воображали, что она выдаст вам результат в должное время. Машина Тьюринга
может через некоторое время оста-
140
Глава 23
новиться и выдать результат или она может никогда не остановиться, и
заранее вы этого не знаете. Нельзя ожидать от машины Тьюринга слишком
многого. В частности, вам не следует ожидать, что вы будете знать,
остановится ли она вообще при данном входном сообщении; не существует
алгоритма, который определял бы это. На самом деле не существует и
алгоритма определения К.-Ч.-сложности сообщений - это один из аспектов
теоремы Геделя, который открыл Чайтин.
Чайтин показал следующее: утверждения типа "Сообщение "ля-ля-ля... "
имеет К.-Ч.-сложность, равную, по крайней мере, N" либо ложны, либо
недоказуемы, когда N является достаточно большим. Достаточно большим -
это насколько большим? Это зависит от аксиом вашей теории. Ваши аксиомы
содержат определенное количество информации (в зависимости от их полной
длины), и вы не сможете доказать, что "ля-ля-ля... " содержит больше
информации, чем используемые вами аксиомы. Разумно, не так ли? Причем это
даже не слишком сложно доказать5.
Много еще можно говорить о теореме Геделя, но, поскольку я не желаю
тонуть сам (и топить вас) в технических деталях, я добавлю еще только
парочку замечаний.
