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, потом — машину со свойствами 1 и 3, наконец, я сконструировал машину со свойствами 2 и 3. Все три машины прекрасно работают — вон там, в портфеле, у меня подробные схемы… Но когда я пытаюсь объединить все три свойства в одной машине, у меня ничего не получается.
— Что же именно у вас не получается? — поинтересовался Крейг.
— Да она вообще не работает! — воскликнул Уолтон с отчаянием. — Когда я ввожу в нее пару чисел (х, у), то вместо того, чтобы выдать мне результат, машина вдруг начинает странно гудеть, как будто в ней происходит нечто вроде короткого замыкания. Как вы думаете, отчего это может быть?
— Да-а, — покачал головой Крейг. — Здесь есть над чем подумать. Правда, сейчас мне надо уйти, меня ждут, но если вы оставите мне свою визитную карточку или просто фамилию и адрес, то я немедленно дам знать, как только во всем этом разберусь.
Через несколько дней инспектор Крейг написал Уолтону письмо. Начиналось оно так:
Дорогой мистер Уолтон!
Благодарю Вас за то, что вы посетили меня и рассказали о машине, которую пытались построить. Честно говоря, я не совсем понимаю, каким образом ваша машина, даже если бы вам действительно удалось ее создать, могла бы решать любые математические задачи, — хотя вы, несомненно, разбираетесь в этом лучше меня. Однако должен вам сказать, что ваш замысел напоминает мне попытку создания вечного двигателя — он также неосуществим! Фактически же дело обстоит гораздо хуже, чем с вечным двигателем.
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52