Случайность и хаос - Рюэль Д.
Скачать (прямая ссылка):
хотят получить представление о том, каковы отвратительные технические
детали теории, даже если они и не хотят сами стать специалистами в этой
области. Конечно же, более доступным является популярный отчет самого
Хокинга:
S.W. Hawking, Л Brief History of Time /Краткая история времени/ (London:
Bantam, 1988).
Глава 21. Информация
1. Поскольку вирус СПИДа является вирусом РНК, этими четырьмя буквами
изначально являются не (Д Т, G, С), а копия, сделанная в этот алфавит
обратной транскриптазой.
2. Для семейства сообщений с вероятностями pi,p2?-- - среднее
количество информации, содержащейся в одном сообщении,
186
Примечания
равно
среднее количество информации = - ^ р^ log р^.
г
Если существует N сообщений с вероятностью 1/N каждое, тогда средняя
информация равна logTV. Во многих случаях теорема Бреймана - МакМиллана
сводит изучение сообщений с разными вероятностями к изучению
равновероятных сообщений. Хорошее техническое обсуждение теории
информации, включающее теорему Бреймана - МакМиллана, см. в P.
Billingsley, Ergodic Theory and Information /Эргодическая теория и
информация/ (New York: John Wiley, 1965).
3. С. Shannon, "А mathematical theory of communication"
/Математическая теория связи/ Bell System Tech. J. 27 (1948): 379-423,
623-56.
4. Для изучения количества информации мелодии необходима статистика,
соответствующая группам 2, 3, 4,... последовательных нот. Но интервалы
между двумя последовательными нотами обеспечивают удобную переоценку
информации.
5. См. ссылку в примечании 1 к главе 19. Безусловно, нужно сравнивать
музыкальные произведения одинаковой длины или делить информацию на длину
произведения.
6. Если говорить конкретно, то необходимо обозначить семейство
разрешенных сообщений, например, прямоугольных картин с постоянным
цветом. (Этот класс содержит мало информации, так как можно выбрать
только размеры прямоугольника и конкретный цвет, так что количество
разнообразных выборов будет не слишком велико.) Может оказаться сложным
явно определить разрешенное семейство сообщений в данной форме искусства
(типа "абстрактной живописи"), но обыкновенно мы интуитивно чувствуем,
насколько свободно или несвободно мы можем, например, писать сонеты или
романы.
Глава 22. Сложность, алгоритмическая
1. См. М. R. Garey and D. S. Johnson, Computers and Intractability
/Компьютеры и трудность обработки/ (New York: Freeman, 1979) . Эта книга
является стандартной работой по алгоритмической сложности и содержит, в
частности, исследование машин Тьюринга.
Примечания
187
2. Эффективный алгоритм для линейного программирования изобрел Л. Г.
Хачьян, а к практике его приспособил Н. Кармаркар. См. примечание 1 к
главе 6, где задачи конечной игры с нулевой суммой, в которой участвуют
два человека, формулируются как задачи линейного программирования.
3. NP означает недетерминистический полиномиал (Nondeter-ministic
Polynomial). Он называется так потому (как рассматривается ниже), что
положительный ответ можно проверить за полиномиальное время, если была
выдвинута (недетерминистически) правильная догадка. Все TVP-полные задачи
являются в равной степени сложными: если вы сумеете решить одну из них,
вы сумеете решить все; значит, квалификация является полной.
4. О спиновых стеклах и неупорядоченных системах см. М. Mezard, G.
Parisi, and М. A. Virasoro, Spin Glass Theory and Beyond /Теория спиновых
стекол и не только/ (Singapore: World Scientific, 1987). Задача спиновых
стекол, как ее определили мы, не рассматривается в книге Гарея и Джонсона
(примечание 1, глава 22), но она близка к задаче SMC ("Simple Max Cut")
("Простой максимальный разрез"), которая считается TVP-полной.
5. Древовидная структура природной эволюции аналогична древовидной
структуре долин в решении Паризи модели спиновых стекол (по этому вопросу
см. Spin Glass Theory and Beyond, описанную в предыдущем примечании).
Судя по всему, эта аналогия поддерживается и на количественном уровне
(см. Н. Epstein and D. Ruelle, "Test of a probabilistic model of
evolutionary success" /Проверка вероятностной модели эволюционного
успеха/ Physics Reports 184 [1989]: 289-92).
Глава 23. Сложность и теорема Геделя
1. Эту историю я услышал от Р. В. Кадисона.
2. Следующая книга (на французском языке) очень полезна для того,
чтобы разобраться в работе Фрейда: J. Laplanche and J.-В. Pontalis,
Vocabulaire de la psychanalyse /Словарь психоанализа/ (Paris: PUF, 1967).
3. Что это значит, когда из аксиом невозможно доказать или
опровергнуть истинность некоторого утверждения? Чтобы это увидеть,
необходимо понять природу игры, которая называется метаматематикой и в
которую играют математические логики. У математиков есть различные теории
А, В,..., каждая из которых основана на системе аксиом, которая считается
непротиворечивой. Например, А может быть аксиоматическим представлением
188
Примечания
арифметики целых чисел, а В - теории множеств. (Гедель показал, что
