Принцесса или тигр?

.

6. Положим

W=NPA—P—R — R—NPA.

Z=R—W, откуда Z=R—NPA—P—R — R — NPA,

Y-R—Z. откуда Y = R — R — NPA — Р— R — R — NPA.

Х = Р— Y. откуда Х = Р— R — R — NPA — Р— R — R-NPA.

Тогда X утверждает доказуемость Y, Y утверждает опровержимость Z, Z утверждает опровержимость W, a W утверждает недоказуемость X (действительно, W утверждает недоказуемость ассоциата выражения Р—R — R — NPA, которым является само высказывание X).

Если W опровержимо, то W ложно; поэтому X доказуемо и, значит, истинно; следовательно, Y доказуемо, а значит, истинно; стало быть, Z опровержимо, а потому ложно. Отсюда сразу следует, что W неопро-

Стр.199

вержимо. Итак, W не может быть опровержимым; значит, W является неопровержимым, и, следовательно, Z будет ложным.

Далее, если W ложно, то W ложно, но неопровержимо. Предположим, что W истинно; тогда X недоказуемо. Если X истинно, то X истинно и недоказуемо. Предположим теперь, что X ложно; тогда Y недоказуемо. Если Y истинно, то Y истинно, но недоказуемо. Предположим, наконец, что Y ложно; тогда Z неопровержимо. Итак, в данном случае Z ложно, но неопровержимо.

Приведенное рассуждение показывает, что либо W ложно и неопровержимо, либо X истинно и недоказуемо, либо Y истинно и недоказуемо, либо Z ложно и неопровержимо.

7. Эта задача фактически представляет собой просто записанный в других обозначениях вариант задачи 1 данной главы!

Мы знаем, что число 32983 в первой машине Мак-Каллоха порождает число 9832983. Следовательно, по условию Мс1 утверждение 832983 истинно в том и только том случае, если утверждение 9832983 доказуемо. Кроме того, по условию Мс2; утверждение 9832983 истинно в том и только том случае, если утверждение 832983 не является истинным. Итак, сопоставляя эти два факта, мы получаем, что утверждение 9832983 истинно в том и только том случае, если оно недоказуемо. Значит, решением является число 9832983.

Если мы сравним эту задачу с задачей 1, то увидим, что цифра 9 играет здесь роль N, цифра 8 соответствует символу Р, цифра 3 соответствует А, а цифра 2 играет роль тире. В самом деле, если мы заменим символы Р, N, А,— соответствующими цифрами 8, 9, 3, 2, то утверждение NPA — NPA (которое является решением задачи 1) трансформируется в число 9832983 (то есть в решение данной задачи!)

8. Прежде всего отметим, что третья машина Мак-Каллоха также подчиняется закону Мак-Каллоха, который гласит, что для любого числа А всегда найдется некое число X, которое порождает число АХ. Доказы-

Стр. 200

вается это следующим образом. Из гл.13 мы знаем, что существует число Н, а имении число 5464,такое что для любого X число Н2Н2 порождает число Х2Х2. (Вспомним также, что число Н2Н2 в данной ситуации порождает само себя; впрочем, к нашей задаче это никакого отношения не имеет.) И теперь произвольное число А и положим Х=Н2АН2), Тогда число X порождает число АН2АН2, которое и есть АХ. Таким образом, X порождает АХ. Итак, для любого числа А число X, порождающее число АХ,— это есть число 54642А54642.