"Нил Стивенсон. Криптономикон" - читать интересную книгу автора

- Как?
- Ничего сложного, Лоуренс, простой шифр. Произвольный. Вместо
уродливой сигмы напиши число 538 и так далее.
- Очень близко к баловству.
- Нет, нет! Потому что Гёдель расставил ловушку. В формулу можно
подставлять числа, да?
- Конечно. Как 2х.
- Да. Можно подставить на место x любое число, и формула его удвоит. Но
если математическую формулу вроде этой для вычисления числа "р" можно
закодировать числом, то ее можно подставить в другую формулу. Формулу в
формулу!
- И это все?
- Нет. Потом он доказал, очень простым способом, что если формулы можно
применить к формулам, то мы вправе сказать: "данное утверждение
недоказуемо". Что страшно удивило Гильберта и других, ожидавших
противоположного результата.
- Этого твоего Гильберта ты уже упоминал?
- Нет, Лоуренс, он появился в нашем разговоре только сейчас.
- Кто он?
- Человек, который задает трудные вопросы. У него их целый список.
Гёдель ответил на один.
- А фон Тьюринг - на другой, - добавил Руди.
- Это еще кто?
- Это я, - сказал Алан. - Только Руди шутит. В Тьюринге вообще-то нет
приставки "фон".
- Сегодня ночью будет. - Руди как-то странно взглянул на Алана. Будь
Лоуренс повзрослее, он бы определил этот взгляд как "страстный".
- Ладно, не томи. На какой вопрос Гильберта ты ответил?
- Entscheidungsproblem* [Проблема разрешимости (нем.).], - сказал Руди.
- То есть?
Алан объяснил:
- Гильберт хотел знать, можно ли в принципе доказать истинность или
ложность любого высказывания.
- Но Гёдель все изменил, - произнес Руди.
- Верно. После Гёделя вопрос стал звучать так: "Можно ли определить,
доказуемо или нет некое - любое - конкретное высказывание?" Другими словами,
есть ли механический процесс, посредством которого мы в состоянии отсеять
доказуемые утверждения от недоказуемых?
- "Механический процесс", Алан, это вообще-то метафора...
- Ладно тебе, Руди. Мы с Лоуренсом не боимся механики.
- Усек, - сказал Лоуренс.
- Что значит "усек"? - спросил Алан.
- Твоя машина - не для дзета-функций, а другая, о которой мы
говорили...
- Она называется Универсальная Машина Тьюринга, - сказал Руди.
- Вся эта хреновина нужна, чтобы отделять недоказуемые утверждения от
доказуемых, верно?
- Вот для чего я придумал ее основную идею, - сказал Алан. - Так что на
вопрос Гильберта ответ уже есть. Теперь я хочу на самом деле ее построить,
чтобы обыграть Руди в шахматы.