Случайность и хаос - Рюэль Д.
Скачать (прямая ссылка):
Быть может, вы огорчились, потому что я сказал, что теорема Геделя
связана со свойствами целых чисел, а вместо них рассмотрел сложность
сообщений. На самом деле логические утверждения (например, касающиеся
сложности сообщений) можно перевести в свойства целых чисел. Это игра,
которую начал Гедель и которая достигла кульминации в том, что известно
как решение "десятой задачи Гильберта"6. А потому неважно, что мы не
говорили о свойствах целых чисел в явном виде.
Сущностью теоремы Геделя в том виде, в каком мы ее рассмотрели, является
тот факт, что, вводя определенную программу, мы не знаем, остановится
машина Тьюринга или нет. Для программ определенной длины машина будет
либо работать до истечения некоторого максимального времени и потом
остановится, либо будет работать вечно и не остановится никогда. Если бы
мы знали максимальное время остановки нашей машина Тьюринга для программы
каждой длины, то мы могли бы определить, для каких программ машина
остановится, а для каких нет. (Просто позвольте машине проработать до
максимального времени остановки для данной длины программы; если она не
остановится к тому времени, то она не остановится никогда). Но суть
проблемы состоит в том, что максимальное время остановки нам не известно.
И мы не можем его знать, потому что оно растет быстрее любой вы-
Сложность и теорема Геделя
141
числимой функции длины программы - быстрее полиномиальной функции,
быстрее экспоненциальной функции, быстрее экспоненциала экспоненциальной
функции...
В предыдущей главе мы решили, что задача является трудноразрешимой, если
вы не смогли ее решить за полиномиальное время (полиномиальное, то есть
относящееся к длине программы). Мы видим, насколько еще более
трудноразрешимыми являются некоторые математические задачи. Нас
интересовала сложность вещей, и теорема Геделя говорит нам, что уже
арифметика целых чисел настолько сложна, насколько мы это можем себе
представить.
Итак, последний вопрос. Как все это связано с темой данной книги? Что
общего у теоремы Геделя со случайностью? Мы знаем, что можно вечно
создавать новые свойства целых чисел, независимые от тех, что уже
известны, но являются ли эти свойства в некотором смысле случайными? И
ответ на это вопрос действительно утвердителен, так как можно создать
последовательность свойств целых чисел, которые произвольно являются
истинными или ложными (это явно сделал Чайтин)7. Другим словами, на
основании свойств целых чисел можно определить последовательность
двоичных разрядов, которые являются 0 или 1 независимо и с вероятностью,
равной 1/2. Это означает лишь то, что никакой объем вычислительной
мощности не даст вам (в среднем) абсолютно точного предсказания
следующего разряда (т. е. фактически эта последовательность достаточно
невычислима).
В странном мире мы живем, не правда ли? По крайней мере, именно такой вид
мира дают нам логики в настоящий момент. И мы к нему привыкаем. Вид может
опять измениться и стать еще более диким... и через некоторое время мы
опять к нему привыкнем8.
Глава 24
ИСТИННЫЙ СМЫСЛ РАЗДЕЛЕНИЯ ПОЛОВ
Мы приближаемся к концу этой книги, и, быть может, вам жаль, что у вас не
было шанса проявить больше инициативы. И действительно, если не считать
покачивания головой и невнятного бормотания, ваше отношение было
несколько пассивным. Давайте это изменим. Сейчас я предлагаю вам заняться
благородным и удовлетворительным делом: созданием жизни.
Мы допустим, что Вы уже создали Звезды, Галактики и все Такое. Написать
несколько Уравнений на Листе Бумаги - это все, что Вам пришлось сделать,
чтобы создать Вселенную, и теперь Вы отправите Свое Сообщение во
Вселенную, вложив в Него Жизнь.
Если вы не возражаете, я больше не стану использовать заглавные буквы и
взгляну на вас и ваше сообщение жизни холодным взглядом ученого. Основной
факт, о котором нельзя забывать, состоит в том, что ваше сообщение жизни
должно одержать победу над огромной хаотичностью. Действительно,
классический хаос, квантовая неопределенность и даже теорема Геделя тайно
замышляют внести случайность в созданную вами вселенную. Как это повлияет
на ваше сообщение?
Ранее мы рассматривали модель спиновых стекол как метафору жизни. Идея
состоит в том, что существует некоторая функция
Е(сообщения)
такая, что ваше сообщение должно пытаться создать максимально (или, по
крайней мере, разумно) много. Мы можем допустить, что ваше сообщение
должно воспроизводить себя и что функция Е связана с вероятностью
воспроизведения сообщения, тождественного (или аналогичного) исходному1.
Функция Е отражает все, что
Истинный смысл разделения полов
143
ваше сообщение знает о вселенной, и, в частности, оно отражает
хаотичность вселенной.
Задача спиновых стекол (добиться максимального Е) является NP-трудной,
как мы это видели в главе, связанной с алгоритмической сложностью. Вы не
станете пытаться найти точный ответ, как не станете и пытаться решить ее
самостоятельно. Вы позволите своему сообщению самому позаботиться о себе,
