— А как именно это определить с помощью числа Н? — спросил Крейг.
— Если бы я нашел число Н, — объяснил Мак — Каллох, — то сначала построил бы такую же машину, как у моего приятеля. Потом, взяв произвольное приемлемое число 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, то есть либо оба они оказываются вечными, либо отмирающими.
Рассмотрим теперь произвольную машину, которая подчиняется правилам 1 и 2 (и, возможно, еще каким-то правилам). Возьмем некоторое число Н. Мы знаем, что, согласно правилам 1 и 2, должно существовать такое число X, которое порождает число НХ (напомним, кстати, что одним из таких чисел является число Н32НЗ). Поскольку число X порождает число НХ, то оба они должны быть либо отмирающими, либо вечными (ведь, как мы только что убедились, их «выживаемость» одинакова). Значит, не может существовать такого числа Н, для которого в случае произвольного X одно из пары чисел Н и НХ было бы отмирающим, а другое — вечным, поскольку для конкретного числа вида Х=Н32НЗ это оказывается совсем не так. Следовательно, ни одна машина, подчиняющаяся правилам 1 и 2, не может решить задачу о своей собственной «выживаемости».
Отметим по ходу дела, что полученный результат оказывается справедливым также для любой машины, которая подчиняется правилам 1 и 4, а в сущности, и для любой машины, которая подчиняется закону Мак-Каллоха. (Кстати говоря, вся эта проблема тесно связана с известной «проблемой останова» для машин Тьюринга, решение которой, как известно, тоже отрицательно.)
Машина, которая так и не была создана
Как-то днем, вскоре после описанных событий, Крейг спокойно сидел дома, в своем кабинете. В дверь робко постучали — это оказалась его квартирная хозяйка.
— Входите, пожалуйста, миссис Хоффман, — пригласил Крейг.
— Простите, мистер Крейг, там вас спрашивает какой-то джентльмен. Только больно уж чудаковато он выглядит, — сказала миссис Хоффман. — Говорит, будто он на пороге величайшего открытия в математике! И еще утверждает, что вас это необычайно заинтересует, и потому он хочет видеть вас немедленно. Что ему сказать?