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. Предположим наконец, что наша система удовлетворяет следующим двум условиям.
Условие Мс1.Для любых чисел X и Y, если число X порождает число Y в первой машине Мак-Каллоха, утверждение 8Х истинно тогда и только тогда, если утверждение Y доказуемо. (Напомним, что число 8Х это не 8, умноженное на X, а цифра 8, за которой стоит число X.)
Условие Мс2.Для любого числа X утверждение 9X истинно тогда и только тогда, если утверждение X не является истинным.
Найдите такое число N, при котором утверждение N истинно, но недоказуемо в данной системе.
8. Предположим, что в условии Mс1 говорится не о «первой машине Мак-Каллоха», а о «третьей машине Мак-Каллоха». Попробуем теперь найти такое утверждение, которое было бы истинным, но недоказуемым.
9. Парадокс ли это?
Вернемся вновь к задаче 1, однако внесем в нее некоторые изменения. Вместо символа Р мы будем использовать символ В (в силу определенных психологических причин — каких именно, станет ясно из дальнейшего). Определение «утверждения» остается тем же, что и раньше, только на этот раз символ Р везде заменяется на символ В. Таким образом, наши утверждения принимают теперь вид: В-X, NB-X, ВА-X, NBA-X. Все утверждения, как и прежде, делятся на две группы — истинные и ложные, причем нам не известно, какие именно из утверждений истинны, а какие — ложны. Далее, вместо машины, печатающей различные утверждения, у нас теперь имеется ученый-логик, который верит одним утверждениям и не верит другим. Когда мы говорим, что наш логик не верит какому-то утверждению, мы вовсе не имеем в виду, что он обязательно сомневается в нем или отвергает его; просто неверно, что он верит в это утверждение. Другими словами, он либо считает его ложным, либо вообще не имеет о нем никакого мнения. Таким образом, символ В (от англ. believe — верить) означает «то, во что верит логик». Тогда для любого выражения X у нас есть четыре интерпретации выражений, содержащих X:
В1: утверждение В-X истинно тогда и только тогда когда логик верит в X;
В2: утверждение NB-X истинно тогда и только тогда когда логик не верит в X;
В3: утверждение ВА-X истинно тогда и только тогда когда логик верит в X–X;
В4: утверждение ВА-X истинно тогда и только тогда, когда логик не верит в X–X.
Предполагая, что наш логик точен, то есть что он не верит в ложные утверждения, мы можем, разумеется, найти некое утверждение, которое является истинным, но о котором логик не знает, что оно истинно. Таким утверждением будет высказывание NBA-NBA (которое говорит нам о том, что логик не верит в ассоциат выражения NBA, имеющий вид NBA-NBA).
А дальше начинается нечто интересное. Предположим, нам известно об этом ученом-логике следующее.
Обстоятельство 1. Наш ученый-логик знает логику не хуже нас с вами. Предположим, что он обладает абсолютными логическими способностями; это означает, что если ему заданы какие-нибудь логические посылки, то он может вывести из них все возможные суждения.
Обстоятельство 2. Логику известно, что выполняются условия В1, В2, В3 и В 4.
Обстоятельство 3. Логик всегда точен, то есть он не верит в ложные утверждения.
Далее, раз логику известно, что имеют место условия В1, В2, В3 и В4, и он может рассуждать так же логично, как мы с вами, ничто не мешает ему провести те же рассуждения, которые провели мы, прежде чем доказали, что утверждение NBA-NBA должно быть истинным. Ясно, что, как только он это проделает, он сразу поверит в утверждение NBA-NBA. Но как только он в него поверит, это утверждение становится опровергнутым, ибо смысл данного утверждения как раз и заключается в том, что наш логик в него не верит, — тем самым в конце концов окажется, что наш логик неточен!
Итак, не приходим ли мы к некоему парадоксу, если принимаем обстоятельства 1, 2 и 3? Конечно, нет, никакого парадокса здесь нет. Просто в последнем абзаце моего рассуждения допущена намеренная неточность! Не могли бы вы ее обнаружить?
Решения
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 опровержимо. (Другой вариант решения — принять за X утверждение РА-R-РА, а за Y — утверждение R-РА-R-РА.)
Далее, если Y доказуемо, то Y истинно, откуда следует, что X опровержимо и, следовательно, ложно, что в свою очередь означает, что Y недоказуемо. Таким образом, допущение о доказуемости Y приводит нас к противоречию; стало быть, оно неверно, и Y недоказуемо. Если же Y недоказуемо, то X ложно. Итак, мы имеем:
(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.
— А как именно это определить с помощью числа Н? — спросил Крейг.
— Если бы я нашел число Н, — объяснил Мак — Каллох, — то сначала построил бы такую же машину, как у моего приятеля. Потом, взяв произвольное приемлемое число X, я ввел бы его в одну из машин; одновременно мой приятель ввел бы число НХ в другую машину. Понятно, что описанный процесс может прекратиться только в одной из машин; если это произойдет в моей машине, я буду знать, что число X — отмирающее; если в машине моего приятеля, то я сразу пойму, что число X — вечное.
— Да ведь вам незачем строить вторую машину, — сказал Фергюссон. — Это можно сделать и на одной машине, просто переключая ее с одного процесса на другой.
— Верно, — согласился Мак-Каллох. — Но только все это пустые рассуждения, пока я не сумел найти число Н. Вполне возможно, что моя машина просто не способна решить задачу о своей собственной «выживаемости», то есть, я хочу сказать, что, быть может, такого числа Н вообще не существует. А может, это я не способен найти такое число. Вот эту то проблему, джентльмены, я и хотел бы обсудить вместе с вами.
— Ну что ж, — сказал Фергюссон, — прежде всего мы должны знать, по каким правилам работает данная машина.
— Всего в ней используется 25 правил, — начал было Мак-Каллох. — Первые два из них — те же самые, что и в моей первой машине.
— Минуточку, — прервал его Фергюссон. — Вы хотите сказать, что машина вашего приятеля подчиняется правилам 1 и 2?
— Вот именно, — ответил Мак-Каллох.
— Тогда мне все ясно, — заявил Фергюссон. — Ни одна машина, в которой действуют правила 1 и 2, не может решить задачу о своей собственной «выживаемости».
— Как же вы сумели так быстро об этом догадаться? — спросил Крейг.
— Я уже сталкивался с подобного рода вещами, — объяснил Фергюссон. — Не так давно в моей работе возникла аналогичная проблема.
И все же, как именно Фергюссон определил, что машина, подчиняющаяся правилам 1 и 2, не может решить задачу о своей собственной «выживаемости»?
Решения
1. Напомним, что число 3223 порождает число 23223, а число 23223 в свою очередь порождает число 3223. Значит, у нас есть два числа, 3223 и 23223, которые порождают друг друга. Отсюда следует, что оба они вечны: ведь если ввести в машину одно из них, то получится второе, а если ввести второе, то получится первое. Ясно, что такой процесс бесконечен.
2. Возьмем два любых числа X и У. Мы будем говорить, что число X приводит к числу У, если X порождает У, или если X порождает какое-то число, которое порождает У, или если X порождает какое-то число, которое порождает другое число, которое в свою очередь порождает У, и т. д. Иначе говоря, если, введя в машину число X, мы на каком-то этапе нашего процесса получим число У, то будем говорить, что число X приводит к числу У. Так, например, число 22222278 приводит к числу 78 фактически на шестом этапе. В более общем виде: если число Т представляет собой произвольную цепочку двоек, то для любого числа X число ТХ в конце концов приводит к X.
Далее, число 32223 не порождает самое себя, но приводит к самому себе, потому что оно порождает число 2232223, которое порождает затем число 232223, а это число в свою очередь вновь порождает 32223. Но раз число 32223 приводит к самому себе, то, стало быть, оно должно быть вечным.
Читатель, по-видимому, уже обратил внимание на следующую закономерность: если число Т состоит целиком из одних двоек, то число ЗТЗ должно приводить к самому себе и, следовательно, будет вечным.
3. Мне известен только один способ решения этой задачи: доказать в общем виде, что если число Т состоит целиком из одних двоек, то число ЗТ32 вечно и, следовательно, частный его случай — число 3232 — тоже является вечным. Этот факт служит иллюстрацией некоторого еще более общего принципа, который используется нами в решении следующей задачи.
Предположим, что у нас имеется определенный класс чисел (неважно, конечный или бесконечный), причем такой, что каждое число из этого класса приводит к некоторому числу из этого же класса (либо к самому себе, либо к другому числу). Тогда все числа, входящие в этот класс, должны быть вечными.
Попробуем воспользоваться этим принципом применительно к нашей задаче. Рассмотрим класс чисел вида ЗТ32, где Т — произвольная цепочка двоек. Покажем, что число ЗТ32 должно приводить к другому числу из этого же класса.
Возьмем сначала число 3232. Оно порождает число 32232, то есть элемент того же класса. Теперь, что нам дает число 32232? Оно порождает число 2322232, которое в свою очередь порождает число 322232, то есть элемент того же класса. А что получается с числом 322232? Оно порождает число 223222232, которое порождает число 23222232, а оно в свою очередь дает нам число 3222232, так что мы опять возвращаемся в указанный класс. В более общем виде: для любой цепочки двоек Т число 32Т32 порождает число Т322Т32, которое приводит к числу 322Т32, опять представляющему собой элемент данного класса. Итак, все числа, входящие в указанный класс, являются вечными.
4. Число 32323 порождает число 3232323, которое порождает число 32323232323, а это последнее в свою очередь порождает число 3232323232323232323. Дальнейшая схема представляется очевидной: любое число, состоящее из повторенного несколько раз числа 32 с тройкой на конце, порождает другое число того же вида (только более длинное), причем все эти числа будут вечными.
5. Прежде всего обратим внимание на следующее обстоятельство: пусть у нас имеются два числа X и Y, такие, что число X порождает число Y. Тогда если Y — отмирающее число, то X тоже должно быть отмирающим, поскольку если Y через какие-то n этапов приводит к неприемлемому числу Z, то X приводит к тому же самому числу Z через n+1 этапов. Кроме того, если Y вечно, то оно никогда не приведет к неприемлемому числу; стало быть, и число X не может привести к неприемлемому числу, поскольку X вообще может приводить к любому числу только через Y. Таким образом, если число X порождает число Y, то «выживаемость» числа X (то есть вечное оно или отмирающее) будет такой же, как и «выживаемость» числа Y, то есть либо оба они оказываются вечными, либо отмирающими.
