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