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


Машина, которая так и не была создана

Как-то днем, вскоре после описанных событий, Крейг спокойно сидел дома, в своем кабинете. В дверь робко постучали — это оказалась его квартирная хозяйка.
— Входите, пожалуйста, миссис Хоффман, — пригласил Крейг.
— Простите, мистер Крейг, там вас спрашивает какой-то джентльмен. Только больно уж чудаковато он выглядит, — сказала миссис Хоффман. — Говорит, будто он на пороге величайшего открытия в математике! И еще утверждает, что вас это необычайно заинтересует, и потому он хочет видеть вас немедленно. Что ему сказать?
— Ну что ж, — несколько помедлив, ответил Крейг. — Проведите его ко мне. У меня как раз найдется полчасика.
Через несколько секунд дверь кабинета распахнулась и в комнату влетел безумного вида человек, смахивавший на изобретателя (это и был изобретатель). Он швырнул свой портфель на диван и, вскинув руки кверху, начал приплясывать, как сумасшедший, приговаривая:
— Нашел! Нашел! Еще чуть-чуть и я стану самым великим математиком на свете! Евклид, Архимед, Гаусс — все канут в Лету! А Ньютон, Лобачевский, Бойаи, Риман — разве…
— Спокойно, спокойно, — не повышая голоса, но достаточно твердо прервал его Крейг. — Что же именно вы нашли?
— Еще не совсем нашел, — отвечал незнакомец уже не так возбужденно. — Но вот-вот найду и, когда найду, стану самым великим математиком всех времен и народов! Имена Галуа, Коши, Дирихле, Кантора…
— Ну хватит! — решительно сказал Крейг. — Может быть, вы все же расскажете мне, что именно вы хотите найти?
— Хочу найти? — воскликнул незнакомец с обидой. — Говорю вам, я почти нашел! Я почти придумал универсальную машину, которая сможет решать любые математические задачи! Имея такую машину, я буду знать все! Я смогу…
— А, мечта Лейбница! — сказал Крейг. — Лейбниц ведь тоже мечтал о такой машине. Боюсь только, что мечта эта неосуществима.
— Лейбниц! — презрительно усмехнулся незнакомец. — Лейбниц! Да он просто не знал, с чего начать! А у меня практически уже есть такая машина! Не хватает только нескольких мелочей… Но давайте я вам лучше поподробней расскажу о своих идеях.
— Я хочу построить некую машину М, — начал объяснения незнакомец (как выяснилось, звали его Уолтон), — с вполне определенными свойствами: сначала вы вводите в машину натуральное число х, потом натуральное число у — и тут машина начинает работать и выдает некоторое новое число, которое мы будем обозначать как М(х, у). Итак, М(х, у) — это результат, который мы имеем на выходе машины М в том случае, если на ее входе в качестве первого числа задать число х, а в качестве второго — число у.
— Пока все ясно, — сказал Крейг.
— Кроме того, — продолжал Уолтон, — под словом «число» я понимаю произвольное положительное целое число, поскольку только эти числа я и буду рассматривать в дальнейшем. Как вам, должно быть, известно, обычно говорят, что два натуральных числа имеют одинаковую четность, если они одновременно либо оба четны, либо оба нечетны; если же одно из них четно, а другое нечетно, то их называют числами с различной четностью.
Теперь для любого числа х мы будем обозначать через х* число вида М(х, х). Так вот, я хочу, чтобы моя машина обладала следующими тремя свойствами.
Свойство 1. Для любого числа a должно существовать некоторое число b, такое, что при любом х число М(х, b) будет иметь ту же самую четность, что и число М(х*,а).
Свойство 2. Для любого числа b должно существовать некоторое число а, такое, что при любом х число М(х, а) будет иметь другую четность по сравнению с числом М(х, b).
Свойство 3. Должно существовать число h, такое, что при любом х число М(х, h) будет иметь ту же самую четность, что и само х.
— Вот такими свойствами должна обладать моя машина, —
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28