Рэймонд Смаллиан - Принцесса или тигр
(1) X ложно;
(2) Y недоказуемо.
Теперь если Y истинно, то Y истинно и недоказуемо. Если же Y ложно, то X неопровержимо (поскольку Y утверждает опровержимость X), и поэтому в данном случае X ложно, но неопровержимо. Следовательно, либо Y истинно, но недоказуемо, либо X ложно, но неопровержимо.
б) Возьмем в качестве X утверждение NP-NRA-NP-NRA, а в качестве Y — утверждение NRA-NP-NRA (или же за X можно принять NPA-NR-NPA, а за Y — NR-NPA-NR-NPA). Тогда, как читатель может убедиться сам, X утверждает недоказуемость Y, а Y утверждает неопровержимость X. Если X опровержимо, то X ложно; тогда Y доказуемо и, значит, Y истинно, откуда следует, что X неопровержимо. Следовательно, X неопровержимо и, кроме того, Y истинно. Если же X ложно, то X ложно и неопровержимо. Если, наконец, X истинно, то Y недоказуемо; поэтому в данном случае Y будет истинным и недоказуемым.
Обсуждение. По аналогии предположим, что на нашем острове, где живут рыцари и плуты, имеются еще два обитателя X и Y, причем X заявляет, будто Y — признанный рыцарь, а Y утверждает, что X — отъявленный плут. Единственный вывод, который можно сделать, — это что один из них (мы не знаем, кто именно) должен оказаться либо непризнанным рыцарем, либо неотъявленным плутом. Точно такая же ситуация будет иметь место, если X станет утверждать, что Y непризнанный рыцарь, а Y заявит, что X — неотъявленный плут.
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 неопровержимо. Итак, 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, которое порождает число АХ. Доказывается это следующим образом. Из гл. 13 мы знаем, что существует число Н, а имении число 5464, такое что для любого X число Н2Н2 порождает число Х2Х2. (Вспомним также, что число Н2Н2 в данной ситуации порождает само себя; впрочем, к нашей задаче это никакого отношения не имеет.) И теперь произвольное число А и положим Х = Н2АН2), Тогда число X порождает число АН2АН2, которое и есть АХ. Таким образом, X порождает АХ. Итак, для любого числа А число X, порождающее число АХ, — это есть число 54642А54642.
Пусть нам требуется найти такое X, которое порождало бы 98Х. Предположим, что это X действительно порождает число 98Х. Тогда утверждение 8Х истинно в том и только том случае, если утверждение 98X доказуемо (согласно условию Мс1); поэтому утверждение 98Х истинно в том и только том случае, если утверждение 98Х недоказуемо (согласно условию Мс2). Значит, утверждение 98 X является истинным, но недоказуемым в данной системе (поскольку система правильна).
Теперь, если в качестве А мы возьмем число 98, то увидим, что числом X, порождающим 98Х, является число 546429854642, Поэтому утверждение 98546429854642 истинно, но недоказуемо в данной системе.
9. Я сообщил вам, что наш логик точен, но я вовсе не говорил, будто он знает, что он точен! Если бы логик знал, что он точен, тогда данная ситуация действительно привела бы нас к противоречию. Поэтому правильный вывод из обстоятельств 1, 2 и 3 вовсе не содержит противоречия: просто-напросто хотя логик и точен, но он не может знать, что он точен.
Эта ситуация определенным образом связана с еще одной теоремой Гёделя, называемой обычно второй теоремой Гёделя о неполноте. Эта теорема (с некоторыми упрощениями) утверждает, что для систем с достаточно богатой структурой (а таковы системы, рассмотренные Гёделем в его пионерской работе), если такая система непротиворечива, то она не может доказать собственную непротиворечивость. Однако это очень глубокий вопрос, и я собираюсь рассмотреть его более подробно в своих последующих книгах.
Вечные отмирающие числа
Однажды вечером Крейг случайно повстречал Мак-Каллоха и Фергюссона. Они давно не виделись, все трое очень обрадовались встрече и решили вместе пойти куда-нибудь поужинать.
— А знаете, — сказал Мак-Каллох, когда ужин подходил к концу, — меня уже давно занимает одна интересная проблема.
— Это какая же? — поинтересовался Фергюссон.
— Дело вот в чем, — продолжал Мак-Каллох. — Когда я занимался изучением различных числовых машин, то столкнулся с тем, что практически в каждой машине одни числа оказываются для нее приемлемыми, а другие нет. Допустим, я ввожу в машину какое-то приемлемое число X. Тогда число Y, которое порождается этим X, вновь оказывается либо приемлемым, либо неприемлемым. Если Y неприемлемо, то на этом весь процесс заканчивается. Если же Y оказывается приемлемым числом, то я опять ввожу его в машину и смотрю, какое число Z выдаст мне машина на этот раз. Если теперь число Z оказывается неприемлемым, то на этом процесс останавливается; если же оно приемлемо, то я вновь ввожу это число в машину и процесс продолжается как минимум еще один цикл. Если я буду повторять такую процедуру снова и снова, то при этом возможны два варианта: либо я в конце концов получу неприемлемое число, либо описанный процесс будет длиться бесконечно. В первом случае я называю число X отмирающим относительно данной конкретной машины, во втором случае число X я называю вечным. Конечно, любое число может быть отмирающим для одной машины и вечным для другой.
— Давай возьмем твою первую машину, — предложил Крейг. — Я могу придумать кучу отмирающих чисел, а не можешь ли ты привести мне пример вечного числа?
— Ну хотя бы число 323,— ответил Мак-Каллох. — Ведь число 323 порождает самое себя и поэтому, сколько бы раз я не вводил его в машину, я всегда буду получать 323. Так что в данном случае процесс явно оказывается бесконечным.
— А ведь верно! — засмеялся Крейг. — Ну хорошо, а существуют ли другие вечные числа?
1. —Тогда, — продолжал Мак-Каллох, — что ты скажешь по поводу числа 3223? Отмирающее оно или вечное?
2. — А как насчет числа 32223? — спросил Фергюссон. — Оно для вашей первой машины — отмирающее или вечное?
Мак-Каллох на некоторое время задумался.
— Это не так трудно определить, — ответил он наконец — Однако я думаю, вам будет интересно разобраться в этом самому.
3. —Можете попробовать еще число 3232,—в свою очередь предложил Мак-Каллох, — попытайтесь определить— отмирающее оно или вечное.
4 — А если взять число 32323? — спросил Крейг. — Отомрет оно или нет?
5 — Все это очень интересно, — сказал Мак-Каллох, — но я еще не добрался до самого главного. А дело вот в чем: один мой приятель придумал весьма хитроумную числовую машину. Он утверждает, будто его машина может выполнять любые операции, на которые только способна числовая машина вообще. Мой друг назвал ее универсальной машиной. И вот оказывается, что есть несколько таких чисел, про которые ни я, ни он не можем сказать—отмирающие они или вечные. Поэтому мне хотелось бы разработать какой-нибудь чисто механический тест, чтобы определять, какие числа отмирающие, а какие — вечные. Правда, пока У меня ничего не выходит. Конкретнее, я пытаюсь найти такое число Н, которое для любого приемлемого числа X давало бы вечное число НХ, если X — отмирающее, и отмирающее число НХ, если X—вечное. Если бы мне это удалось, то я сразу смог бы определить, отмирающее ли или вечное любое приемлемое число X.
