Принцесса или тигр - Смаллиан Р.М.
Скачать (прямая ссылка):
4. Число 32323 порождает число 3232323, которое порождает число 32323232323, а это последнее в свою очередь порождает число 3232323232323232323. Дальнейшая схема представляется очевидной: любое число, состоящее из повторенного несколько раз числа 32 с тройкой на конце, порождает другое число того же вида (только более длинное), причем все эти числа будут вечными.
206
5. Прежде всего обратим внимание на следующее обстоятельство: пусть у нас имеются два числа X и У, такие, что число X порождает число У. Тогда если У—отмирающее число, то X тоже должно быть отмирающим, поскольку если У через какие-то п этапов приводит к неприемлемому числу X, то X приводит к тому же самому числу Z через п +1 этапов. Кроме того, если У вечно, то оно никогда не приведет к неприемлемому числу; стало быть, и число X не может привести к неприемлемому числу, поскольку X вообще может приводить к любому числу только через У. Таким образом, если число X порождает число У, то «выживаемость» числа X (то есть вечное оно или отмирающее) будет такой же, как и «выживаемость» числа У, то есть либо оба они оказываются вечными, либо отмирающими.
Рассмотрим теперь произвольную машину, которая подчиняется правилам 1 и 2 (и, возможно, еще каким-то правилам). Возьмем некоторое число Н. Мы знаем, что, согласно правилам 1 и 2, должно существовать такое число X, которое порождает число НХ (напомним, кстати, что одним из таких чисел является число Н32НЗ). Поскольку число X порождает число НХ, то оба они должны быть либо отмирающими, либо вечными (ведь, как мы только что убедились, их «выживаемость» одинакова). Значит, не может существовать такого числа Н, для которого в случае произвольного X одно из пары чисел Н и НХ было бы отмирающим, а другое—вечным, поскольку для конкретного числа вида Х=Н32НЗ это оказывается совсем не так. Следовательно, ни одна машина, подчиняющаяся правилам 1 и 2, не может решить задачу о своей собственной «выживаемости».
Отметим по ходу дела, что полученный результат оказывается справедливым также для любой машины, которая подчиняется правилам 1 и 4, а в сущности, и для любой машины, которая подчиняется закону МакКаллоха. (Кстати говоря, вся эта проблема тесно связана с известной «проблемой останова» для машин Тьюринга, решение которой, как известно, тоже отрицательно.)
207
Машина, которая так и не была создана
Как-то днем, вскоре после описанных событий, Крейг спокойно сидел дома, в своем кабинете. В дверь робко постучали—это оказалась его квартирная хозяйка.
— Входите, пожалуйста, миссис Хоффман,— пригласил Крейг.
— Простите, мистер Крейг, там вас спрашивает какой-то джентльмен. Только больно уж чудаковато он выглядит,— сказала миссис Хоффман.— Говорит, будто он на пороге величайшего открытия в математике! И еще утверждает, что вас это необычайно заинтересует, и потому он хочет видеть вас немедленно. Что ему сказать?
— Ну что ж,—несколько помедлив, ответил Крейг.—Проведите его ко мне. У меня как раз найдется полчасика.
Через несколько секунд дверь кабинета распахнулась и в комнату влетел безумного вида человек, смахивавший на изобретателя (это и был изобретатель). Он швырнул свой портфель на диван и, вскинув руки кверху, начал приплясывать, как сумасшедший, приговаривая:
— Нашел! Нашел! Еще чуть-чуть и я стану самым великим математиком на свете! Евклид, Архимед, Гаусс—все канут в Лету! А Ньютон, Лобачевский, Бойаи, Риман—разве...
— Спокойно, спокойно,— не повышая голоса, но достаточно твердо прервал его Крейг.— Что же именно вы нашли?
— Еще не совсем нашел,— отвечал незнакомец уже не так возбужденно.— Но вот-вот найду и, когда найду, стану самым великим математиком всех времен и народов! Имена Галуа, Коши, Дирихле, Кантора...
— Ну хватит!—решительно сказал Крейг.— Может быть, вы все же расскажете мне, что именно вы хотите найти?
208
— Хочу наити?—воскликнул незнакомец с обидой.— Говорю вам, я почти нашел! Я почти придумал универсальную машину, которая сможет решать любые математические задачи! Имея такую машину, я буду знать все! Я смогу...
— А, мечта Лейбница!—сказал Крейг.— Лейбниц ведь тоже мечтал о такой машине. Боюсь только, что мечта эта неосуществима.
— Лейбниц!—презрительно усмехнулся незнакомец.—Лейбниц! Да он просто не знал, с чего начать! А у меня практически уже есть такая машина! Не хватает только нескольких мелочей... Но давайте я вам лучше поподробней расскажу о своих идеях.
— Я хочу построить некую машину М,—начал объяснения незнакомец (как выяснилось, звали его Уолтон),— с вполне определенными свойствами: сначала вы вводите в машину натуральное число х, потом натуральное число у—и тут машина начинает работать и выдает некоторое новое число, которое мы будем обозначать как М(х, у). Итак, М(х, у)—это результат, который мы имеем на выходе машины М в том случае, если на ее входе в качестве первого числа задать число х, а в качестве второго — число у.
— Пока все ясно,— сказал Крейг.
— Кроме того,— продолжал Уолтон,— под словом «число» я понимаю произвольное положительное целое число, поскольку только эти числа я и буду рассматривать в дальнейшем. Как вам, должно быть, известно, обычно говорят, что два натуральных числа имеют одинаковую четность, если они одновременно либо оба четны, либо оба нечетны; если жё одно из них четно, а другое нечетно, то их называют числами с различной четностью.
