Не могли бы вы ее обнаружить?

Решения

1. Для любого выражения X утверждение NPA-X означает, что ассоциат выражения X не допускает распечатки. В частности, утверждение NPA-NPA означает, что ассоциат выражения NPA не допускает распечатки. Но ассоциатом NPA является само утверждение NPA-NPA! Следовательно, высказывание NPA-NPA утверждает невозможность собственной распечатки; другими словами, это высказывание истинно в том и только том случае, если оно не допускает распечатки. Отсюда следует, что оно либо истинно, но не допускает распечатки, либо ложно, но распечатку допускает. Последний случай исключается, поскольку машина является точной. Следовательно, нам остается лишь первая возможность: данное утверждение истинно, но не может быть напечатано машиной.
2. Выберем в качестве X утверждение Р-NPA-Р-NPA, а в качестве Y-NPA-Р-NPA. Утверждение X (которое имеет вид Р-Y) говорит нам о том, что утверждение Y допускает распечатку. Смысл самого Y сводится к тому, что ассоциат утверждения Р-NPA не допускает распечатки. Но ассоциатом утверждения Р-NPA является X, значит, Y говорит нам о том, что X не допускает распечатки. (Между прочим, можно построить и другие X и Y, обладающие теми же свойствами: например, если взять в качестве X утверждение РА-NP-РА, а в качестве Y — утверждение NP-РА-NP-РА.)
Таким образом, у нас имеются два утверждения X и Y, причем X утверждает, что Y допускает распечатку, а Y утверждает, что X не допускает распечатки.
Предположим теперь, что X допускает распечатку. Тогда утверждение X окажется истинным, а это будет означать, что утверждение Y допускает распечатку. Но тогда Y окажется истинным, откуда будет следовать, что X распечатки не допускает. Тем самым мы приходим к противоречию, поскольку в данном случае X оказывается одновременно и допускающим, и не допускающим распечатку; следовательно, утверждение X не может быть напечатано. Далее, раз X не допускает распечатки, а Y как раз это и утверждает, то, стало быть, утверждение Y является истинным. Таким образом, мы имеем:
(1) X не допускает распечатки;
(2) Y истинно.
Наконец, утверждение X может быть либо истинным, либо ложным. Если X истинно, тогда, согласно (1), X истинно, но не допускает распечатки. Если же X ложно, тогда Y не допускает распечатки, поскольку само X говорит нам о том, что Y допускает распечатку. Значит, в данном случае Y истинно — согласно (2) — и не допускает распечатки. Итак, либо X, либо Y истинно и не допускает распечатки — однако определить, какое именно из этих двух выражений истинно и не допускает распечатки, оказывается невозможно.
Обсуждение. Описанная ситуация аналогична следующей ситуации, возникшей на острове рыцарей и плутов: пусть на острове имеются два обитателя X и Y, причем X утверждает, что Y — признанный рыцарь, а У утверждает, что X — непризнанный рыцарь. Единственное заключение, которое мы можем сделать — это, что один из них является непризнанным рыцарем, но кто именно, сказать невозможно.
Подобная ситуация рассматривается в последней главе моей книги «Как же называется эта книга?» в разделе «Дважды гёделевы острова», к которому мы и отсылаем читателя.
3. Положим Z = PA-P-NP-РА.
Далее, положим Y = NP-Z (то есть Y = NP-РА-Р-NP-РА).
Положим, наконец, Х = Р-Y (то есть Х = Р-NP-PA-P-NP-PA).
Из этих выражений сразу ясно: X утверждает, что Y допускает распечатку, а Y говорит нам о том, что Z не допускает распечатки. Что же касается Z, то оно утверждает, что допускает распечатку ассоциат утверждения Р-NP-РА; но ассоциат Р-NP-РА есть утверждение Р-NP-РА-Р-NP-РА, которое в свою очередь и есть X! Итак, Z утверждает, что X допускает распечатку.
Таким образом, X утверждает, что Y допускает распечатку, Y утверждает, что Z не допускает распечатки, a Z утверждает, что распечатку допускает X. Посмотрим теперь, что же из этого следует.
Предположим, что Z допускает распечатку. Тогда Z истинно, откуда следует, что X допускает распечатку, а значит, является истинным; это в свою очередь означает, что Y допускает распечатку и, следовательно, является истинным. Если же Y истинно, то, стало быть, Z не должно допускать распечатки. Таким образом, мы приходим к противоречию: если Z допускает распечатку, то оно ее не допускает. Значит, Z не допускает распечатки, и поэтому Y является истинным. Итак, нам известно, что:
(1) Z не допускает распечатки;
(2) Y истинно.
Далее, X может быть либо истинным, либо ложным. Предположим, что X истинно. Если Z ложно, то тогда X не допускает распечатки, а это означает, что X истинно, но не допускает распечатки. Если же Z истинно, то тогда, поскольку, согласно (1), оно не допускает распечатки, Z истинно, но не допускает распечатки. Итак, если X истинно, то либо X, либо Z истинно, но не допускает распечатки. Если же X ложно, тогда Y не допускает распечатки и, следовательно, Y истинно — согласно (2) — и не допускает распечатки.
Итак: если X истинно, то по крайней мере одно из двух утверждений X и Z является истинным, но не допускающим распечатки. Если же X ложно, то истинным, но не допускающим распечатки, оказывается утверждение Y.
4. Пусть S есть утверждение вида RA-RA. Оно говорит нам о том, что ассоциат выражения RA (а ассоциат RA есть само S!) является опровержимым; следовательно, S истинно в том и только том случае, когда S опровержимо. Поскольку S не может быть одновременно и истинным и опровержимым, значит оно ложно, но неопровержимо.
5. а) Выберем в качестве X утверждение Р-RA-Р-RA, а в качестве Y — утверждение RA-Р-RA. Ясно, что X утверждает доказуемость Y, а Y утверждает опровержимость ассоциата выражения Р-RA (ассоциат Р-RA есть в данном случае просто само X). Итак, X утверждает, что Y доказуемо, а Y утверждает, что X опровержимо.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69