хотим сказать, что допускает распечатку выражение AN, то пишем Р-AN. Предположим теперь, нам нужно сказать, что выражение — X допускает распечатку. Правильно ли будет записать эту фразу как Р-Х? Нет, ведь запись Р-X означает, что выражение X допускает распечатку. Поэтому чтобы сказать, что допускает распечатку выражение — X, нужно написать Р-X.
Рассмотрим еще несколько примеров: запись Р- означает, что «-» допускает распечатку, запись РА- означает, что выражение (ассоциат выражения-) допускает распечатку; запись Р- также означает, что «-» допускает распечатку; запись NРА-Р-А означает, что ассоциат выражения — Р-А не допускает распечатки, или, другими словами, что не допускает распечатки выражение — Р-А-Р-А. То же самое означает и запись вида NP-Р-А-Р-А.
Утверждением будем называть любое выражение одного из следующих четырех типов: Р-X, NP-X, РА-X или NPA-X, где X — любое выражение. Утверждение Р-X мы будем называть истинным, если X допускает распечатку, и ложным, если X с допускает распечатки. Утверждение NP-X мы будем называть истинным, если X не допускает распечатки, и ложным, если X эту распечатку допускает, утверждение РА-X будет называться истинным, если ассоциат выражения X допускает распечатку, и ложным, если ассоциат этого X распечатки не допускает. Наконец, утверждение NA-X мы будем называть истинным, если ассоциат выражения X не допускает распечатки, и ложным, если ассоциат этого X распечатку допускает. Итак, мы дали точное определение истинности и ложности для утверждений всех четырех видов. Отсюда следует, что для любого выражения X справедливы:
Правило 1. Утверждение Р-X истинно тогда и только тогда, когда выражение X допускает распечатку (на машине).
Правило 2. Утверждение РА-X истинно тогда и только тогда, когда выражение X–X допускает распечатку.
Правило 3. Утверждение NP-X истинно тогда и только тогда, когда выражение X не допускает распечатки.
Правило 4. Утверждение NPA-X истинно тогда и только тогда, когда выражение X–X не допускает распечатки
Удивительное дело! Машина печатает утверждения, которые представляют собой не что иное, как суждения о том, что она сама может и что не может напечатать! В этом смысле машина говорит о себе (или точнее, печатает утверждения о самой себе).
Пусть теперь нам известно, что машина на 100 % точна, то есть она не может выдать нам ложное утверждение, печатая только истинные утверждения. Отсюда вытекает ряд следствий. Например, если машина в один прекрасный день напечатает утверждение Р-X, то, значит, она должна напечатать и выражение X, потому что раз она может напечатать утверждение Р-X, то, стало быть, это утверждение истинно, а это означает, что выражение X допускает распечатку. Значит, действительно, машина рано или поздно должна распечатать выражение X.
Аналогично, если машина выдаст нам утверждение РА-X, тогда (поскольку утверждение РА-X должно быть истинным) она должна напечатать нам также и выражение X–X. Помимо этого, если машина напечатает утверждение NP-X, тогда она не сможет напечатать утверждение Р-X, поскольку эти два высказывания не могут одновременно являться истинными: ведь первое из них утверждает, что машина не может напечатать выражение X, а второе — что машина может его напечатать.
Следующая задача высвечивает идею Гёделя так хорошо, что лучше трудно себе представить.
1. На редкость гёделева задача.
Найдите истинное утверждение, которое машина не может напечатать!
2. Дважды гёделева головоломка.
Все исходные условия остаются прежними — и, в частности, то, что машина абсолютно точна. Пусть у нас имеются утверждение X и утверждение Y; одно из них является истинным, но не допускающим распечатки; однако, пользуясь лишь условиями, вытекающими из правил 1–4, мы не можем сказать, какое именно это утверждение, X или Y. Можете ли вы найти такие утверждения X и Y? (Подсказка: найти такие утверждения X и Y, чтобы утверждение X говорило нам о том, что Y допускает распечатку, а в утверждении Y говорилось бы о том, что X не допускает распечатки. Существуют два способа построения таких утверждений, причем оба они связаны с законами Фергюссона!)
3. Трижды гёделева проблема.
Построить такие утверждения X, Y и Z, чтобы X говорило о том, что Y допускает распечатку, Y говорило бы о том, что не допускает распечатки, a Z — о том, что X в свою очередь вновь допускает распечатку, и показать, что по крайней мере одно из этих утверждений (правда, нельзя сказать, какое именно) должно быть истинным, но не допускающим распечатки на машине.
Добавим к четырем нашим символам еще один — символ R. Таким образом, теперь у нас пять символов: Р, R, N, А, — . Пусть нам даны две машины, М1 и М2, каждая из которых может печатать различные выражения, составленные из этих пяти символов. При этом под символом Р в данном случае мы будем подразумевать «допускающий распечатку первой машиной», а под символом R — «допускающий распечатку второй машиной». Таким образом, запись Р-X означает, что выражение X допускает распечатку первой машиной, а запись R-X — что выражение X допускает распечатку второй машиной. Запись РА-X означает, что ассоциат выражения X допускает распечатку первой машиной, а запись RA-X показывает, что ассоциат выражения X допускает распечатку второй машиной. Наконец, «фразы» NP-X, NR-X, NPA-X, NRA-X говорят соответственно о следующем: выражение X не допускает распечатки первой машиной; выражение X не допускает распечатки второй машиной; выражение X–X не допускает распечатки первой машиной; выражение X–X не допускает распечатки второй машиной. Под утверждением мы будем теперь понимать любое выражение одного из следующих восьми типов: Р-X, R-X, NP-X, NR-X, РА-Х, RA-X, NPA-X, NRA-X. Кроме того, пусть нам известно, что первая машина печатает только истинные утверждения, а вторая — только ложные. Условимся называть некоторое утверждение доказуемым в том и только том случае, если оно допускает распечатку первой машиной, и ложным — в том и только том случае, если оно: может быть напечатано второй машиной. Таким образом, символ Р означает «доказуемый» (от англ. provable), а символ R — «опровержимый» (от англ. refutable).
4. Найдите утверждение, которое было бы ложным, но неопровержимым.
5. Имеются такие два утверждения X и Y, что одно из них (правда, нам не известно, какое именно) должно быть либо истинным, но недоказуемым, либо ложным, но неопровержимым (мы не знаем, каким именно). Такие пары можно строить двумя способами, и соответственно я предлагаю вашему вниманию две задачи:
а. Найдите такие высказывания X и Y, чтобы X утверждало доказуемость Y, a Y утверждало опровержимость X. Далее, покажите, что одно из них (мы не можем сказать, какое именно) либо истинно, но недоказуемо, либо ложно, но неопровержимо.
б. Найдите такие высказывания X и Y, чтобы Х утверждало недоказуемость Y, а Y утверждало неопровержимость X. Далее покажите, что одно из этих высказываний, X или Y (мы не можем сказать, какое именно), либо истинно, но недоказуемо, либо ложно, но неопровержимо.
6. А теперь рассмотрим задачу с четырьмя неизвестными! Пусть нам требуется найти такие высказывания X, Y, Z и W, чтобы X утверждало доказуемость Y, Y утверждало опровержимость Z. Z утверждало опровержимость W, a W утверждало бы неопровержимость X. Покажите, что одно из этих четырех высказываний должно быть либо истинным, но недоказуемым, либо ложным, но неопровержимым (хотя, какое из этих четырех будет именно таким высказыванием, сказать невозможно).
Возможно, читатель уже отметил определенное сходство приведенных выше задач с некоторыми свойствами первой машины Мак-Каллоха. В самом деле, работа этой машины оказывается связанной с теоремой Гёделя, и вот каким образом.
7. Пусть у нас имеется некоторая математическая система, приводящая к набору утверждений, одни из которых называются истинными, а другие — доказуемыми. Мы предполагаем также, что эта система правильная, то есть каждое доказуемое в ней утверждение является истинным. Далее, пусть каждому числу N ставится в соответствие некоторое утверждение, которое мы будем называть утверждением N.
