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

— Верно, — согласился Мак-Каллох. — Но только все это пустые рассуждения, пока я не сумел найти число Н. Вполне возможно, что моя машина просто не способна решить задачу о своей собственной «выживаемости», то есть, я хочу сказать, что, быть может, такого числа Н вообще не существует. А может, это я не способен найти такое число. Вот эту то проблему, джентльмены, я и хотел бы обсудить вместе с вами.

— Ну что ж, — сказал Фергюссон, — прежде всего мы должны знать, по каким правилам работает данная машина.

— Всего в ней используется 25 правил, — начал было Мак-Каллох. — Первые два из них — те же самые, что и в моей первой машине.

— Минуточку, — прервал его Фергюссон. — Вы хотите сказать, что машина вашего приятеля подчиняется правилам 1 и 2?

— Вот именно, — ответил Мак-Каллох.

— Тогда мне все ясно, — заявил Фергюссон. — Ни одна машина, в которой действуют правила 1 и 2, не может решить задачу о своей собственной «выживаемости».

— Как же вы сумели так быстро об этом догадаться? — спросил Крейг.

— Я уже сталкивался с подобного рода вещами, — объяснил Фергюссон. — Не так давно в моей работе возникла аналогичная проблема.

И все же, как именно Фергюссон определил, что машина, подчиняющаяся правилам 1 и 2, не может решить задачу о своей собственной «выживаемости»?

Решения

1. Напомним, что число 3223 порождает число 23223, а число 23223 в свою очередь порождает число 3223. Значит, у нас есть два числа, 3223 и 23223, которые порождают друг друга. Отсюда следует, что оба они вечны: ведь если ввести в машину одно из них, то получится второе, а если ввести второе, то получится первое. Ясно, что такой процесс бесконечен.

2. Возьмем два любых числа X и Y. Мы будем говорить, что число X приводит к числу Y, если X порождает Y, или если X порождает какое-то число, которое порождает Y, или если X порождает какое-то число, которое порождает другое число, которое в свою очередь порождает Y, и т. д. Иначе говоря, если, введя в машину число X, мы на каком-то этапе нашего процесса получим число Y, то будем говорить, что число X приводит к числу Y. Так, например, число 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 с тройкой на конце, порождает другое число того же вида (только более длинное), причем все эти числа будут вечными.