Принцесса или тигр?

После того как инспектор Крейг возвратился в Лондон, он поначалу потратил массу времени, пытаясь разгадать загадку сейфа из Монте-Карло, но потом, так ничего и не добившись, счел за благо на некоторое время отложить злополучную задачу в сторону и немножко развеяться. Тут ему пришла в голову мысль навестить своего старого приятеля Нормана Мак-Каллоха, которого он не встречал уже несколько лет. Они подружились, еще будучи студентами Оксфордского университета, и Крейг всегда с большой теплотой вспоминал те дни и своего друга — отличного парня, правда, немного чудаковатого, который постоянно выдумывал всякого рода технические курьезы. И хотя наш рассказ относится ко времени, когда современные ЭВМ еще не были изобретены, Мак-Каллоху уже в ту пору удалось сконструировать нечто вроде механического счетно-решающего устройства, но, конечно, по нынешним меркам, весьма примитивного.

— В свое время я здорово развлекался с этой штукой, — объяснил приятелю Мак-Каллох. — Правда, никак не могу придумать, к чему бы полезному ее приспособить, но зато она обладает всякими занятными свойствами.

— Что же она умеет делать? — поинтересовался Крейг.

— А вот что, — бодро начал Мак-Каллох. — Ты вводишь в машину заданное число, а через некоторое время она сама выдает тебе число.

— То же самое число или какое-нибудь другое? — спросил Крейг.

— Это зависит от того, какое число в нее ввести.

— Понятно, — почесал в затылке Крейг.

— Кроме того, — продолжал Мак-Каллох, — моя машина воспринимает не все числа, а лишь некоторые из них. Поэтому те числа, которые ее устраивают, я буду называть допустимыми числами.

— Вся эта терминология звучит весьма логичной, — согласился Крейг, — но позволь мне узнать, какие числа для машины являются допустимыми, а какие нет. Имеется ли какое-нибудь правило на этот счет? И еще: существует ли определенное правило относительно того, какое же число выдает машина, если только ты решил, какое именно допустимое число в нее ввести?

— Дело тут не совсем так, — пояснил Мак-Каллох. — Решить ввести число еще недостаточно, надо действительно его ввести.

— Это понятно, — поправился Крейг. — Я лишь хотел спросить, известно ли заранее, какое число выдаст твоя машина, если в нее уже введено исходное число?

— Ну, конечно, — ответил Мак-Каллох. — Моя машина — это ведь не устройство для получения случайных чисел! Она действует по строго определенным законам. А теперь я объясню тебе правила ее работы, — продолжал Мак-Каллох. — Прежде всего под числом я понимаю произвольное целое положительное число; ведь моя нынешняя машина не умеет оперировать с отрицательными величинами и с дробями. Заданное число N при этом записывается обычным способом в виде некоторой последовательности цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Вместе с тем моя машина может манипулировать только с числами, в которых нет нуля, например с числами вида 23 или 5492, но никак не с числами вида 502 или 3250607. Кроме того, если нам даны два числа N и M, то под NM мы понимаем вовсе не N, умноженное на M! Символом NM обозначается число, полученное следующим образом: вначале записываются цифры числа N, причем в том же порядке, в каком они следуют в N, а потом к ним последовательно приписываются цифры числа M. Так, например, если N равно 23, а M равно 728, то символом NM мы будем обозначать число 23728. Или же если N = 4, а M = 39, то под NM мы будем понимать число 439.

— Вот уж совершенно необычная операция с числами! — удивился Крейг.

— Ты прав, — согласился Мак-Каллох. — Но именно эту операцию машина понимает лучше всего. А теперь я объясню тебе некоторые правила ее работы. Кстати, мы говорим, что число X порождает число Y, имея в виду, что X является допустимым числом и что если число X вводится в машину, то Y есть то число, которое оно выдает. Так вот, первое правило таково:

Правило 1. Для любого числа X число 2X (то есть 2, за которым следует X, а не 2, умноженное на X!) является допустимым числом, причем число 2X порождает число X. Например, число 253 порождает число 53, 27482 порождает 7482, 23985 порождает 3985 и т. д. Иными словами, если я ввожу в машину число 2X, то она отбрасывает двойку в начале и выдает нам то, что остается, а именно — число X.

— Ну, это совсем просто, — заметил Крейг. — А каковы остальные правила?

— Машина использует только два правила, — продолжал Мак-Каллох. — Но сначала я хотел бы разъяснить еще кое-что. Так, для любого числа X исключительно важную роль играет число X2X; это число я называю ассоциатом числа X. Например, ассоциатом числа 7 является 727, а ассоциатом числа 594 будет 5942594. А теперь другое правило:

Правило 2. Для любых чисел X и Y справедливо следующее утверждение: если число X порождает число Y, то число 3X порождает ассоциат числа Y.

Например, согласно правилу 1, число 27 порождает 7; следовательно, число 327 порождает ассоциат числа 7, то есть число 727. Точно так же 2586 порождает 586; поэтому 32586 порождает ассоциат числа 586, то есть 5862586.

В этот момент Мак-Каллох ввел в машину число 32586. После неимоверного скрежета и лязга машина, в конце концов, действительно выдала число 5862586.

— Вообще-то ее нужно чуточку смазать, — заметил Мак-Каллох. — А пока давай рассмотрим еще пару примеров, чтобы выяснить, насколько ты усвоил оба моих правила. Допустим, я ввожу в машину число 3327. Что она нам выдаст? Мы уже знаем, что число 327 порождает число 727, а число 3327 порождает ассоциат числа 727, то есть число 7272727. Какое же число порождается числом 33327? Так вот, если 3327 порождает 7272727 (как мы только что убедились), то 33327 должно порождать ассоциат числа 7272727, то есть 727272727272727. Еще один пример: 259 порождает 59, 3259 порождает 59259, 33259 порождает 59259259259, и, наконец, 333259 порождает 59259259259259259259259.

— Это понятно, — согласился Крейг. — Но пока единственные числа, которыми ты пользовался до сих пор и которые, по всей видимости, действительно что-то «порождают», — это числа, начинающиеся с цифры 2 или 3. А как быть с числами, которые начинаются, скажем, с четверки?

— Видишь ли, моя машина действительно воспринимает только числа, начинающиеся с цифры 2 или 3, но даже среди них не все числа оказываются допустимыми. Когда-нибудь я построю машину побольше, чтобы она могла воспринимать большее количество чисел.

— А какие числа, начинающиеся с цифры 2 или 3, оказываются неприемлемыми для твоей машины? — спросил Крейг.

— Ну, например, не является допустимым число 2, поскольку оно не попадает под действие ни правила 1, ни правила 2; однако любое многоразрядное число, начинающееся с цифры 2, является допустимым. Не будет, например, допустимым число, состоящее из одних только троек. Кроме того, не являются допустимыми числа вида 32, 332 или числа, задаваемые в виде произвольной цепочки троек, за которыми следует цифра 2. В то же время для любого числа X допустимыми будут числа 2X, 32X, 332X и т. д. Короче говоря, допустимыми числами являются только числа вида 2X, 32X, 332X, 3332X, а также любая цепочка троек, за которыми следуют цифры 2X. Далее, поскольку число 2X порождает X, а число 32X порождает ассоциат числа X, то число 332X в свою очередь порождает ассоциат ассоциата числа X — число, которое логично называть двойным ассоциатом числа X, а соответственно число 3332X будет давать нам ассоциат ассоциата числа X — это число будем называть тройным ассоциатом числа X — и т. д.

— Вот теперь я понял все до конца, — удовлетворенно заметил Крейг. — Правда, мне бы хотелось еще узнать, о каких это забавных свойствах твоей машины ты упоминал?

— Тут-то мы как раз и приходим к различного рода комбинаторным головоломкам, — пояснил Мак-Каллох. — О некоторых из них я и хочу тебе рассказать!

1. — Начнем с самого простого примера, — сказал Мак-Каллох. — Пусть имеется число N, которое порождает само себя; значит, когда ты вводишь его в машину, она выдает тебе то же самое число N. Не мог бы ты найти такое число?

2. — Прекрасно, — одобрил Мак-Каллох, когда Крейг показал ему свое решение. — А теперь еще об одной интересной особенности этой машины. Пусть имеется число N, которое порождает ассоциат самого себя; другими словами, если ты вводишь в машину число N, то она выдает тебе число N2N. Не сможешь ли ты отыскать это число?

Эта задача показалась Крейгу несколько труднее предыдущей, но в конце концов он справился и с ней. А вы сумеете ее решить?

3. — Превосходно, — сказал Мак-Каллох, взглянув на решение Крейга. — Единственно, что хотелось бы мне знать, — это каким путем ты шел, чтобы найти исходное число N: так сказать, методом «тыка» или же ты действовал по заранее намеченному плану? И кроме того, является ли найденное тобой N единственно возможным числом, порождающим ассоциат самого себя, или же существуют и другие такие числа?

Тогда Крейг рассказал о своем методе отыскания числа N в последней задаче, а также ответил на вопрос Мак-Каллоха о том, существуют ли другие возможные решения этой задачи. Скорее всего, ход суждений Крейга должен заинтересовать читателя; более того, он существенно облегчает нахождение решений нескольких задач этой главы.

4. — Кстати, по поводу моего последнего вопроса, — сказал Мак-Каллох. — Как ты решил первую задачу? Существуют ли еще какие-нибудь числа, которые порождают сами себя?

Ответ Крейга приведен в решениях.

5. — Далее, — продолжал Мак-Каллох, — имеется число N, которое порождает число 7N (то есть за семеркой следует N). Мог бы ты его найти?

6. — Рассмотрим еще один вопрос, — сказал Мак-Каллох. — Существует ли такое число N, чтобы число 3N порождало ассоциат самого числа N?

7. — А существует ли такое N, — спросил Мак-Каллох, — которое порождает ассоциат числа 3N?

8. — Пожалуй, самая интересная особенность моей машины заключается в том, — сказал Мак-Каллох, — что для любого числа А существует некое число Y, которое порождает число AY. Как доказать это утверждение, и как по заданному числу А найти такое число Y?

Примечание. Этот принцип, и в самом деле очень простой, на практике оказывается еще более важным, нежели предполагал в тот момент Мак-Каллох! В этой книге мы столкнемся с ним еще не раз, и поэтому в дальнейшем будем называть его законом Мак-Каллоха.

9. — Далее, — продолжал Мак-Каллох, — всегда ли для сданного числа А существует некое число Y, которое порождает ассоциат числа АY? Существует ли, например, число, которое порождает ассоциат числа 56Y, и если это так, то что это за число?

10. — Еще один интересный факт, — сказал Мак-Каллох, — заключается в том, что существует некоторое число N, которое порождает двойной ассоциат самого себя. Можешь ли ты найти это число?

11. — Кроме того, — сказал Мак-Каллох, — для любого заданного числа А существует число X, которое порождает двойной ассоциат числа АХ. Не мог бы ты сообразить, как найти такое число X, если число А нам задано? К примеру, как найти число X, которое порождает двойной ассоциат числа 78X?

А вот еще несколько задач, с которыми Мак-Каллох познакомил в тот день Крейга. (За исключением последних, эти задачи не имеют особого теоретического значения, однако читателю, может быть, доставит удовольствие повозиться с ними)

12. Найти число N, такое, чтобы число 3N порождало число 3N.

13. Найти число N, такое, чтобы число 3N порождало число 2N.

14. Найти число N, такое, чтобы число 3N порождало число 32N.

15. Существует ли такое число N, для которого числа NNN2 и 3N2 порождали бы одно и то же число?

16. Существует ли такое число N, ассоциат которого порождал бы число NN? Существует ли несколько таких чисел N?

17. Существует ли такое число N, для которого число NN порождало бы ассоциат этого N?

18. Найти число N, такое, чтобы ассоциат числа N порождал двойной ассоциат N.

19. Найти число N, которое порождает число N23.

20. Один отрицательный результат.

— Знаешь, — сказал Мак-Каллох, — я довольно долго пытался найти число N, которое порождает число N2, однако до сих пор все мои попытки не увенчались успехом. Интересно бы узнать, такое число на самом деле не существует или же у меня просто не хватает сообразительности, чтобы его отыскать?

Эта задача сразу завладела вниманием Крейга. Он тут же вытащил записную книжку и карандаш и погрузился в размышления. Спустя некоторое время он сказал:

— Не трать понапрасну силы, такое число просто не может существовать.

Как Крейг догадался об этом?

Решения

1. Таким числом является, например, число 323. В самом деле, поскольку число 23 порождает число 3 (согласно правилу 1), то, согласно правилу 2, число 323 должно порождать ассоциат числа 3, а это и есть 323 — как раз то же самое число!

Существуют ли другие такие числа?

По поводу ответа Крейга на этот вопрос смотри решение задачи 4.

2. Числом, которое нашел Крейг, было 33233. Действительно, любое число вида 332X порождает двойной ассоциат X; так, число 33233 порождает двойной ассоциат числа 33 — то есть ассоциат ассоциата числа 33. Далее, ассоциат числа 33 есть исходное число 11233, и, следовательно, двойной ассоциат числа 33 есть ассоциат числа 33233. Итак, число 33233 порождают ассоциат числа 33233, или свой собственный ассоциат.

Как же было найдено это число, и является ли полученное решение единственным? Крейг дает ответы на эти вопросы при решении следующей задачи.

3. Здесь рассказывается о том, как Крейг отыскал решение задачи 2, а также о том, как он сумел ответить на вопрос, существуют ли какие-либо другие решения этой задачи. Тут я предоставлю слово ему самому:

«Моя задача заключалась в том, чтобы найти число N, которое порождает число N2N. Ясно, что это число должно иметь вид 2X, 32X, 332X, 3332X и т. д., причем мне нужно было отыскать X. Подошло бы в данном случае число вида 2X? Совершенно очевидно, что нет, поскольку число 2X порождает число X, которое, понятно, является более коротким (содержит меньше цифр), чем ассоциат числа 2X. Поэтому ни одно число вида 2X никак не могло оказаться подходящим.

Что можно сказать по поводу числа вида 32X? Оно также порождает ассоциат числа X, который, очевидно, содержит меньшее число цифр, нежели ассоциат числа 32X.

Теперь попробуем число вида 332X. Это число порождает двойной ассоциат числа X, который имеет вид Х2X2X2X, тогда как нам необходимо получить ассоциат числа 332X, то есть число, которое записывается в форме 332X2332X. Далее, может ли число Х2X2X2X оказаться тем же самым числом, что и 332X2332X? Прежде всего, нужно сравнить относительную длину этих чисел. Так, если h — количество цифр в числе X, то число Х2X2X2X должно иметь 4h + 3 цифр (поскольку в нем четыре X и три двойки); в то же время число 332X2332X имеет 2h +7 цифр. Может ли 4h + 3 равняться 2h + 7? Да, но только в том случае, когда h = 2. Итак, что касается длины, то число вида 332X вполне может оказаться для нас подходящим, но лишь при условии, если количество цифр в X равняется двум.

Существуют ли еще какие-нибудь возможности? Посмотрим, например, что можно сказать по поводу числа вида 332X. Такое число порождает тройной ассоциат числа X, который представляет собой число вида Х2X2X2X2X2X2X2X, тогда как нам необходимо получить ассоциат числа 3332X, который записывается как 3332X23332X. Могут ли эти числа оказаться одинаковыми? Вновь обозначая через h длину числа X, находим, что число Х2X2X2X2X2X2X2X имеет 8h + 7 цифр; в то же время число 3332X23332X имеет 2h + 9 цифр. Равенство 8h + 7 = 2h + 9 может выполняться, только если h = 1/3, и, следовательно, в данном случае целочисленного значения не существует. Итак, числа вида 3332X нам также не подходят.

Наконец, что можно сказать относительно числа вида 33332X? С одной стороны, это число порождает четверной ассоциат числа X, который имеет длину 16h + 15; с другой стороны, сам ассоциат числа X имеет длину 2h + 11. Ясно, что для любого целого положительного h выражение 16h + 15 больше, чем 2h + 11, и, значит, число вида 33332X порождает нечто слишком для нас большое.

Если мы теперь возьмем число, начинающееся не с 4, а с 5 троек, то несоответствие между длиной числа, которое оно вроде бы должно было порождать, и длиной числа, которое оно порождает на самом деле, окажется еще больше, а если мы возьмем число, начинающееся с 6 или более троек, то это несоответствие станет совсем большим. Таким образом, нам остается снова вернуться к числу 332X как к единственно возможному решению задачи, причем X в этом случае должен быть числом, состоящим из 2 цифр. Итак, искомое число N должно иметь вид 332ab, где а и b — одиночные цифры, подлежащие определению.

Ясно, что число 332ab порождает двойной ассоциат числа ab, или число аb2аb2аb2аb. При этом необходимо, чтобы число 332ab порождало ассоциат числа 332аb, который записывается как 332ab2332ab. Могут ли эти два числа оказаться одинаковыми? Для ответа на этот вопрос попробуем сравнить их на соответствие цифр:

аb2аb2аb2аb

332аb2332аb.

Сравнивая первые цифры каждого числа, мы видим, что а обязательно должно быть тройкой. Сравнение вторых цифр дает нам, что b также должно оказаться двойкой. Итак, число N = 33233 является решением нашей задачи и притом единственным».

4. — По правде говоря, — признался Крейг, — первую задачу я решал почти интуитивно; чтобы найти число 323, я не пользовался никаким специальным методом. К тому же я пока не успел обдумать вопрос, существует ли какое-либо иное число, которое порождало бы само себя.

— Однако, как мне кажется, ответы на эти вопросы не потребуют слишком много усилий. В самом деле, попробуем, к примеру, выяснить, не могло бы нам подойти какое-нибудь число вида 332X. Такое число должно было бы порождать двойной ассоциат числа X, который представляет собой число вида Х2X2X2X и имеет длину 4h + 3, где h — длина числа X. С другой стороны, нам необходимо взять такое число, чтобы оно порождало число 332X, которое в свою очередь имеет длину h + 3? Вполне очевидно, что при любых положительных h величина 4h + 3 всегда больше, чем h + З, и потому число 332X будет порождать число, в котором окажется слишком много цифр. То же самое можно сказать, по поводу числа вида 3332X, а также чисел, начинающихся с четырех и более троек, для них соответствующие расхождения по длине окажутся еще большими. Значит, единственной возможностью для нас остается число вида 32X (очевидно, что число вида 2X нам также не годится, поскольку оно не может порождать само себя — ведь оно порождает число X). Далее, число 32X порождает число X2X, и, кроме того, требуется, чтобы оно порождало само себя, то есть опять 32X. Поэтому числа 32X и Х2X должны совпадать. Обозначим через h длину числа X, тогда число 32X имеет длину h + 2, а число X2X — длину 2h + 1. При этом должно выполняться условие 2h + 1 = h + 2, откуда сразу следует, что h равно 1. Стало быть, число X состоит из одной-единственной цифры. Наконец, для какой цифры а имеет место условие a2a = 32a? Ясно, что а в этом случае должно быть тройкой. Итак, число 323 является единственным решением данной задачи.

5. Возьмем в качестве N число 3273. Это число порождает ассоциат числа 73, то есть число 73273, которое в свою очередь можно представить как 7N. Итак, число 73273 есть решение нашей задачи. (Кроме того, это решение — единственное, что легко можно показать с помощью сравнительного анализа соответствующих длин, подробно обсуждавшегося в последних двух задачах.)

6. Поскольку число 323 порождает само себя, то число 3323 должно порождать ассоциат числа 323. Итак, если положить N = 323, тогда число 3N действительно порождает ассоциат числи N. (Это решение является единственным.)

7. Решением будет число 332333. Проверка: положим N равным этому числу. Тогда оно порождает двойной ассоциат числа 333, который в свою очередь является ассоциатом числа 3332333 — или, иными словами, ассоциатом числа 3N.

8. Очевидно, что эта задача представляет собой прямое обобщение задачи 5. Там мы видели, что при N = 3273 число N порождает число 7N. Цифра 7 не играет в данном случае никакой особой роли. Действительно, для любого числа А справедливо условие: если мы положим Y = 32A3, то число Y будет порождать число AY (поскольку оно порождает ассоциат числа A3, который записывается как A32A3 и который в свою очередь представляет собой число АY). Итак, например, если мы хотим найти число Y, которое порождало бы число 837Y, то мы должны выбрать Y равным 328373.

Указанный факт, как выяснится ниже, имеет важное теоретическое значение!

9. Ответом на поставленный вопрос будет «да». Возьмем в качестве Y число 332A33. Это число порождает двойной ассоциат числа АЗЗ, который в свою очередь является ассоциатом числа A332A33. Но число A332A33 и есть АY; следовательно, число Y порождает ассоциат числа АY.

Для частного примера, предложенного Мак-Каллохом (найти число Y, которое порождало бы ассоциат числа 56Y), решением будет число Y = 3325633.

10. Решением является число 3332333. Оно порождает тройной ассоциат числа 333, который является двойным ассоциатом ассоциата числа 333. При этом ассоциат числа 333 есть число 3332333, и, стало быть, число 3332333 порождает двойной ассоциат числа 3332333.

Заметим общую систему: число 323 порождает само себя, число 33233 порождает свой ассоциат, число 332333 порождает двойной ассоциат самого себя. Далее, число 333323333 порождает свой тройной ассоциат, число 33333233333 порождает четверной ассоциат самого себя и т. д. (Во всем этом читатель вполне может убедиться сам.)

11. Решением является X = 3332333. Это число порождает тройной ассоциат числа A333, который является двойным ассоциатом ассоциата числа A333. При этом ассоциатом числа А333 оказывается число А3332АЗЗЗ, которое в свою очередь и есть АХ. Итак, число X порождает двойной ассоциат числа АХ.

В частном случае, когда А = 78, решением будет число 333278333.

12. Очевидно, что ответом будет N = 23. (Ведь мы уже знаем, что число 323 порождает само себя, поэтому, положив N = 23, мы действительно имеем, что число 3N порождает число 3N.)

13. Ответ: N = 22.

14. Ответ: N = 232.

15. Конечно, N = 2.

16. В этом случае вполне подойдет любая цепочка двоек.

17. Да; например, N = 32.

18. Положить N = 33.

19. Положить N = 32323.

20. Как читатель легко может удостовериться сам, любое число, начинающееся с двух или более троек, будет порождать число большей длины, нежели число N2. (Например, если N — число вида 332X, и h — длина числа X, то само число N будет порождать двойной ассоциат числа X, который имеет длину 4h + 3, в то время как само число N2 имеет длину h + 4). Точно так же нам никак не подойдет ни одно число N вида 2X, поскольку если и существует некое число N, которое порождает число N2, то оно обязательно должно быть вида 32X. Далее, число 32X порождает число Х2X, тогда как нам требуется получить число 32X2. Если X2X представляет собой то же самое число, что и 32X2, то, обозначая, как обычно, через h длину числа X, мы должны прийти к условию 2h + 1 = h + 3, откуда следует, что h = 2. Итак, единственным числом, которое могло бы нас устроить (если, конечно, таковые существуют), должно быть число вида 32аb, где а и b — одиночные цифры, подлежащие определению ниже. Далее, число 32ab порождает число аb2ab, тогда как нам нужно получить число 32аb2. Итак, могут ли числа ab2ab и 32аb2 оказаться одним и тем же числом? Попробуем сравнить их цифру за цифрой:

ab2ab

32ab2.

Сравнивая первые цифры, мы получаем, что а = 3; из сравнения же третьих цифр имеем, что а = 2. Полученное противоречие доказывает, что наша задача неразрешима. Итак, не существует такого числа N, которое порождало бы число N2!

Спустя две недели Крейг снова навестил Мак-Каллоха.

— Слыхал, что ты построил новый вариант своей машины, — сказал Крейг. — Наши общие друзья рассказывали мне, будто твоя новая машина способна проделывать какие-то удивительные вещи. Это правда?

— Совершенно верно, — ответил Мак-Каллох не без гордости. — Моя новая машина, как и раньше, работает в соответствии с правилами 1 и 2, и, кроме того, в нее введены два новых правила. Однако я только что заварил свежего чая — давай выпьем по чашечке, прежде чем я познакомлю тебя с новыми правилами.

После отличного чая с восхитительными сдобными булочками Мак-Каллох приступил к делу:

— Под обращением некоторого числа я понимаю число, цифры которого записаны в обратном порядке; например, обращение числа 5934 есть число 4395. Вот первое из моих новых правил.

Правило 3. Для любых чисел X и Y справедливо следующее: если число X порождает число Y, то число 4X порождает обращение числа Y.

— Позволь мне проиллюстрировать это правило таким примером, — продолжал Мак-Каллох. — Выбери какое-нибудь произвольное число Y.

— Согласен, — сказал Крейг. — Допустим, я выбрал число 7695.

— Прекрасно. А теперь возьмем число X, которое порождает число 7695, а именно число 27695, потом введем в машину число 427695 и посмотрим, что получится. Мак-Каллох ввел в машину число 427695, а та выдала, разумеется, 5967 — обращение 7695.

— Прежде чем познакомить тебя со следующим правилом, — сказал Мак-Каллох, — я хочу продемонстрировать еще несколько операций, которые моя машина может проделывать с помощью правила 3, конечно, в совокупности с правилами 1 и 2.

1. — Ты, конечно, помнишь, — сказал Мак-Каллох, — что число 323 порождает само себя. Так вот, для моей старой машины, в которую еще не было заложено правило 3, а использовались лишь правила 1 и 2, — число 323 было единственным числом, которое могло порождать самое себя. Для моей теперешней машины ситуация оказывается несколько иной. Можешь ли ты найти какое-нибудь другое число, которое порождало бы самое себя? Кроме того, сколько существует таких чисел?

Решение этой задачи не отняло у Крейга много времени. А вы сумеете ее решить? (Ответ Крейга приведен в разделе «Решения».)

2. — Это было превосходно, — одобрительно сказал Мак-Каллох, внимательно выслушав пояснения Крейга. — Тогда позволь задать тебе другую задачу. Я называю число симметричным, если оно читается одинаково в ту и другую сторону, то есть если оно равно своему обращению. Так, например, числа вида 58385 или 7447 — симметричны. Числа, не являющиеся симметричными, я называю несимметричными — например, такие, как 46733 или 3251. Очевидно, что существует число, которое порождает обращение самого себя — это число 323; действительно, оно порождает само себя и к тому же симметрично. Для моей первой машины, в которую не было заложено правило 3, не существовало такого несимметричного числа, которое порождало бы свое собственное обращение. Однако в случае использования правила 3 такое число все-таки существует — и на самом деле даже не одно. Можешь ли ты найти такое число?

3. — Кроме того, — сказал Мак-Каллох, — существуют числа, которые порождают ассоциаты своих собственных обращений. Можешь ли ты найти такое число?

— А теперь, — продолжал Мак-Каллох, — сформулируем еще одно новое правило.

Правило 4. Если число X порождает число Y, то число 5X порождает число YY.

При этом напомню, что число YY называется повторением числа Y.

Затем Мак-Каллох предложил Крейгу рассмотреть иве новые задачи.

4. Найти число, которое порождает повторение самого.

5. Найти число, которое порождает обращение повторения самого себя.

6. — Вот странно, — удивился Мак-Каллох, когда Крейг показал ему решение задачи 5. — А у меня получился другой ответ — правда, тоже число, состоящее из семи цифр.

Действительно, существуют два семизначных числа, каждое из которых порождает обращение своего собственного повторения. Можете ли вы найти второе из лих чисел?

7. — Для любого X, — сказал Мак-Каллох, — число 52X, понятно, порождает повторение числа X. Не мог бы ты найти такое X, для которого число 5X порождало бы повторение самого X?

Крейг некоторое время размышлял, а потом внезапно рассмеялся: настолько очевидным оказалось решение!

8. — А теперь, — сказал Мак-Каллох, — пусть имеется число, которое порождает повторение ассоциата самого себя. Не мог бы ты найти это число?

9. — Кроме того, — продолжал Мак-Каллох, — существует число, которое порождает ассоциат своего собственного повторения. Можешь ли ты его найти?

— А знаешь, — вдруг сказал Крейг, — я только сейчас сообразил, что все эти задачи могут быть решены, если исходить из некоторого общего принципа. Стоит лишь его понять, как оказывается возможным решать не только те задачи, которые ты мне задавал, но и массу других!

— Например, — продолжал Крейг, — должно существовать число, которое порождает повторение обращения своего собственного ассоциата, или, к примеру, число, которое порождает ассоциат повторения своего собственного обращения, или еще число, которое…

— Поразительно, — прервал его Мак-Каллох. — Я пробовал было отыскать несколько таких чисел, но у меня ничего не вышло. Что же это за числа?

— Ты научишься находить их мгновенно, как толь ко узнаешь, что это за принцип!

— Да что же это за принцип? — взмолился Мак-Каллох.

— И это не все, — продолжал Крейг, которому доставляло явное удовольствие разыгрывать Мак-Каллоха. — Я еще могу найти число X, которое порождает повторение обращения двоимого ассоциата X, или число Y, порождающее обращение двойного ассоциата числа YYYY, или число Z, которое…

— Хватит-хватит! — воскликнул Мак-Каллох. — А почему ты все-таки не хочешь мне сказать, в чем заключается твой принцип, а уж потом перейти к приложениям?

— Ну ладно, — согласился Крейг.

Тут инспектор взял лежавший на столе блокнот, вынул ручку и усадил Мак-Каллоха рядом с собой, с тем чтобы его друг мог видеть, что он пишет.

— Прежде всего, — начал Крейг, — я полагаю, что ты знаком с понятием операции над числами, как, например, операция прибавления единицы к данному числу, или операция умножения числа на 3, или операция возведения данного числа в квадрат, или, что имеет более близкое отношение к твоей машине, операция взятия обращения заданного числа или операции получения повторения и ассоциата некоторого числа, или же, наконец, более сложные операции, как, например, операция построения обращения повторения ассоциата некоторого числа. При этом буквой F будет обозначаться некоторая произвольная операция, а запись F(X), где X — заданное число (мы будем читать Это выражение как «эф от икс»), будет означать результат выполнения операции F над числом X. Все это как ты прекрасно понимаешь, — вполне обычные математические обозначения. Итак, к примеру, если F есть операция обращения, то число F(X) есть обращение числа X; если же F будет обозначать операцию повторения, а выражение F(X) будет повторением числа X и так далее.

Пусть теперь имеются определенные числа — а фактически любые числа, составленные из цифр 3, 4 или 5, — я их буду называть операционными числами, поскольку они определяют операции, которые может выполнять твоя машина. Пусть M — некоторое число, состоящее из цифр 3, 4 или 5, и пусть F — произвольная операция. Я буду говорить, что число M определяет операцию F, имея в виду, что для любых двух чисел X и Y, в случае если X порождает Y, число M(X) порождает число F(Y). Например, если число X порождает число Y, то число 4X порождает обращение числа Y (согласно правилу 3), и поэтому я буду говорить, что число 4 определяет или обозначает операцию обращения данного числа. Аналогичным образом в соответствии с правилом 4 число 5 определяет операцию повторения, а число 3 — операцию ассоциации, то есть операцию получения ассоциата данного числа. Далее, предположим, что F представляет собой операцию, которая, если ее выполнить над числом X, дает нам ассоциат повторения X. Другими словами, F(X) есть ассоциат повторения числа X. Существует ли число M, которое описывает эту операцию, и если да, то что это за число?

— Очевидно, 35, — ответил Мак-Каллох, — потому что если число X порождает число Y, то число 5X порождает повторение числа Y; значит, число 35X порождает ассоциат повторения Y. Таким образом, число 35 обозначает операцию получения ассоциата повторения некоторого заданного числа X.

— Совершенно верно, — подтвердил Крейг. — А теперь, когда мы определили, каким образом число M представляет собой ту или иную операцию, мы будем называть эту операцию операцией M. Так, например, операция 4 будет операцией обращения, операция 5 представляет собой операцию повторения, операция 35 является операцией получения ассоциата повторения и так далее.

Вместе с тем возникает вопрос, — продолжал он, — возможно ли, чтобы два различных числа описывали одну и ту же операцию? Иначе, могут ли существовать операционные числа M и N, такие, что при M, не равном N, операция M оказывается тождественной операции N?

Мак-Каллох на мгновение задумался.

— Ну, конечно, — сказал он. — Ведь, например, числа 45 и 54 различны, однако они определяют собой одну и ту же операцию, поскольку обращение повторения некоторого числа есть то же самое, что и повторение его обращения.

— Правильно, — согласился Крейг, — хотя, по правде говоря, я имел в виду совсем другой пример. Прежде всего, какую операцию описывает число 44?

— Ну, это ясно, — ответил Мак-Каллох, — Операция 44, если ею подействовать на заданное число X, дает нам обращение обращения этого числа, то есть само X. Правда, я не знаю, как назвать такую операцию, которая при воздействии на число X дает нам само это число.

— В математике такая операция называется обычно операцией тождества, — продолжал свои объяснения Крейг, — и поэтому число 44 будет определять собой именно операцию тождества. Но ту же самую операцию будет определять и число 4444 или, например, любое другое число, составленное из четного количества четверок. Таким образом, существует бесконечно много чисел, описывающих подобную операцию. А вообще говоря, если задано некоторое операционное число M и если оно следует за четным количеством четверок или предшествует ему (или же имеет место и то и другое одновременно), то это число M описывает ту же самую операцию, что и само отдельно взятое M.

— Понятно, — кивнул Мак-Каллох.

— А теперь, — пояснил далее Крейг, — если нам заданно операционное число M и произвольное число X, то, чтобы обозначить результат воздействия операции M на число X, я буду просто писать M(X). Например, число 3(X) будет представлять собой ассоциат X, 4(X) будет обращением числа X, 5(X) окажется повторением числа X, а число 435(X) будет представлять собой вращение ассоциата повторения числа X. Понятны тебе эти обозначения?

— Вполне, — ответил Мак-Каллох.

— Надеюсь, теперь ты не будешь путать запись M(X) с записью MX. Ведь первая из них обозначает результат воздействия операции M на число X, в то время как вторая утверждает лишь то, что за числом M следует число X, — а это совсем разные вещи! Например, запись 3(5) обозначает вовсе не 35, а 525.

— Это мне тоже понятно, — сказал Мак-Каллох. — Однако не может ли случиться так — хотя бы в силу чистой случайности, — чтобы число M(X) совпадало с MX?

— Интересный вопрос, — ответил Крейг. — Мне нужно его обдумать!

— Может, сначала выпьем еще по чашечке чаю? — предложил Мак-Каллох.

— С удовольствием! — согласился Крейг.

Пока наши друзья наслаждаются чаем, мне хотелось бы предложить вам несколько занимательных задач с операционными числами. Они позволят читателям приобрести необходимый опыт в использовании обозначений типа M(X), которые будут играть важную роль при дальнейшем изложении.

10. Ответом на последний (математический!) вопрос Мак-Каллоха будет «да»: действительно существуют операционное число M и некоторое число X, такие, что M(X) = MХ. Не могли бы вы найти их?

11. Существует ли операционное число M, для которого M(М) = M?

12. Найти операционное число M и заданное число X, для которых M(X) = ХХХ.

13. Найти операционное число M и число X, для которых M(X) = M + 2.

14. Найти M и X, для которых число M(X) было бы повторением числа MX.

15. Найти операционные числа M и N, для которых M(N) оказалось бы повторением N(M).

16. Найти два различных операционных числа M и N, для которых M(N) = N(M).

17. Не могли бы вы отыскать два операционных числа M и N, для которых M(N) = N(M) + 39?

18. Что можно сказать по поводу двух операционных чисел M и N, для которых M(N) = N(M) + 492?

19. Найти два различных операционных числа M и N, для которых выполняются условия M(N) = MМ и N(M) = NN.

— Ты так и не рассказал мне, в чем же состоит твой принцип, — сказал Мак-Каллох, когда друзья покончили с чаем. — Полагаю, что об операционных числах и операциях мы заговорили именно в связи с этим принципом?

— Ну, конечно, — отвечал Крейг. — Теперь, я думаю, ты легко сможешь понять идею этого принципа. Помнишь задачи, которые ты предлагал мне раньше? Ну, например, найти число X, которое порождает повторение самого себя. Иначе говоря, мы искали некое число X, которое порождает 5(X). Или, пытаясь найти некоторое число X, которое порождает свой собственный ассоциат, мы искали число X, порождающее число 3(X). Далее в свою очередь вспомним, что число X, порождающее обращение числа X, есть число, которое порождает 4(X). Вместе с тем все эти задачи представляют собой частные случаи одного общего принципа, который заключается в следующем: для любого операционного числа M должно существовать некое число X, которое порождает М(X). Другими словами, для любой заданной операции F, которую может выполнять твоя машина, — то есть для любой операции F, описываемой определенным операционным числом, — должно существовать число X, которое порождает F(X).

Более того, — продолжал Крейг, — если задано какое-то операционное число M, то существует очень простой способ найти такое X, которое порождает М(X). Зная этот общий способ, можно найти, например, число X, которое порождает 543(X), — то есть решить задачу нахождения числа X, порождающего повторение обращения ассоциата этого X; или найти такое X, которое порождает 354(X), — то есть решить задачу нахождения числа, порождающего ассоциат повторения своего собственного обращения. Или, как я уже упоминал, можно найти такое X, которое порождает повторение обращения двойного ассоциата X, — другими словами, найти X, порождающее 5433(X). Если не знаешь этого способа, то решать эти задачи оказывается крайне затруднительным, если же воспользоваться моим принципом — то это будут не задачи, а детские игрушки.

— Я — весь внимание, — сказал Мак-Каллох. — Но что же это за такой замечательный способ?

— Сейчас объясню, — ответил Крейг, — но сначала давай разберем поподробнее одно вполне элементарное обстоятельство, а именно: для любого операционного числа M и для любых чисел Y и Z, если число Y порождает число Z, то МY порождает M(Z). Например если Y порождает Z, то 3Y порождает 3(Z), то есть ассоциат Z; 4Y порождает 4(Z); 5Y порождает 5(Z); 34Y порождает 34(Z) и т. д. Точно так же для любого операционного числа M, если Y порождает Z, то МY порождает М(Z). В частности, если такое Y, порождающее Z, оказывается равным 2Z, тогда всегда справедливо утверждение, что M2Z порождает M(Z). Например, число 32Z порождает число 3(Z) — ассоциат Z; число 42Z порождает число 4(Z), то есть при любом операционном числе M число M2Z порождает число M(Z). Собственно говоря, мы даже могли бы определить M(Z) как число, порождаемое числом M2Z.

— Это все понятно, — сказал Мак-Каллох.

— Прекрасно, — сказал Крейг, — однако этот факт легко забывается, поэтому разреши мне повторить его еще раз, с тем чтобы он хорошенько отложился у тебя в голове.

Итак, утверждение 1: для любого операционного числа M и для любых чисел Y и Z, если число Y порождает число Z, число МY порождает число M(Z). В частности, число M2Z порождает число M(Z).

— Отсюда, — продолжал Крейг, — а также из того факта, который ты обнаружил для своей первой машины и который справедлив и для нынешней, очевидно следует, что для любого заданного операционного числа M должно существовать некое число X, порождающее М(X), — то есть в данном случае число X порождает результат применения операции M к числу X. При этом, зная число M, такое X можно легко найти с помощью простого и вполне общего правила.

20. Итак, Крейг открыл важное правило, которое мы в дальнейшем будем называть принципом Крейга, а именно: для любого операционного числа M всегда существует некоторое число X, такое, что оно порождает М(X). Как же доказать принцип Крейга и как при заданном числе M найти число X? Например, какое число X порождает 543(X)? Или какое число X порождает повторение обращения ассоциата X? Или, наконец, какое X порождает ассоциат повторения обращения X — то есть какое X порождает 354(X)?

— Я приготовил для тебя еще несколько задачек, — сказал Мак-Каллох, — однако сегодня уже поздно. Оставайся-ка ночевать у меня. А завтра мы с тобой поговорим подробнее.

У Крейга как раз было несколько свободных дней, и поэтому он с удовольствием принял приглашение Мак-Каллоха.

Наутро после плотного завтрака — а хозяин оказался человеком очень гостеприимным — Мак-Каллох предложил Крейгу следующие задачи.

21. Найти число X, которое порождает число 7X7X.

22. Найти число X, которое порождает обращение числа 9X.

23. Найти число X, которое порождает ассоциат числа 89X.

— Очень мило! — воскликнул Крейг, после того как покончил с решением последней задачи. — Ни одну из их задач нельзя решить с помощью того принципа, о котором я тебе рассказывал вчера.

— Вот именно! — рассмеялся Мак-Каллох.

— И все-таки, — возразил Крейг, — решение всех грех задач подчиняется некой общей идее: во-первых, конкретные числа 7, 5 и 89 не играют никакой роли; для любого данного числа А существует определенное число X, которое порождает повторение числа АХ, еще какое-то X порождает обращение АХ; наконец, есть X, порождающее ассоциат числа АХ. Кроме того, существует также некое число X, которое порождает повторение обращения числа АХ или, например, обращение ассоциата АХ. Фактически это означает, что для любого операционного числа M и для любого заданного числа А должно существовать некоторое число X, которое порождает М(АХ), то есть число, полученное в результате применения операции M к числу АХ.

24. Крейг, разумеется, был прав: для любого операционного числа M и для любого заданного числа А должно найтись некоторое число X, которое порождает число М(АХ). Будем называть это правило вторым принципом Крейга. Как же доказать этот принцип? И как при заданном операционном числе M и заданном А найти в явном виде такое число X, которое порождает М(АХ)?

25. — Мне только что пришел в голову еще один вопрос, — сказал Мак-Каллох. — Пусть для любого числа X величина X обозначает обращение этого X. Можешь ли ты найти такое число X, которое порождает Х67? (Иначе, существует ли такое число X, которое порождает обращение числа X, за которым следует число 67?) В общем виде этот вопрос можно сформулировать так: действительно ли для любого числа А существует некоторое число X, которое порождает ХА?

26. — Мне в голову пришел еще один вопрос, — сказал Мак-Каллох. — Существует ли такое число X, которое порождает повторение числа Х67? Или, в более общем виде: действительно ли для любого числа А существует такое число X, которое порождает повторение числа ХА? Или, если задать вопрос в еще более общем виде: действительно ли для любого числа А и для любого операционного числа M должно существовать некоторое число X, которое порождает M(ХА)?

Обсуждение. Принцип Крейга справедлив не только для второй машины Мак-Каллоха, но и для первой — а в сущности и для любой машины, в которую заложены правила 1 и 2. Это означает, что, как бы мы ни расширяли первую машину Мак-Каллоха, вводя в нее новые правила, работа результирующего устройства все равно будет подчиняться принципу Крейга (а фактически обоим его принципам).

Первый принцип Крейга связан с одним из знаменитых результатов теории вычислимых функций, известным под названием теоремы о рекурсии (или, как ее иногда называют, теоремы о неподвижной точке). С помощью правил 1 и 2, предложенных Мак-Каллохом, этот результат получается, пожалуй, наиболее простым способом. Кроме того, эти правила обладают еще одним занятным свойством (связанным уже с другим знаменитым результатом теории вычислимых функций, известным под названием теоремы о двойной рекурсии), о котором пойдет речь в следующей главе. Наконец, все эти сведения имеют отношение к теории самовоспроизводящихся машин и теории клонирования.

Решения

1. — С помощью твоей теперешней машины можно получить бесконечное множество чисел, которые порождают сами себя, — сказал Крейг.

— Это верно, — согласился Мак-Каллох. — Но как ты это докажешь?

— Начнем с того, — сказал Крейг, — что будем называть некое число SA числом, если оно обладает тем свойством, что для любых чисел X и Y в случае, если X порождает Y, число SX порождает ассоциат Y. До того как ты ввел свое новое правило, единственным А-числом у нас было число 3. Однако для твоей нынешней машины существует бесконечное множество А-чисел, причем для любого А-числа S число S2S обязательно должно порождать само себя, поскольку число S2S порождает ассоциат числа S, который и есть S2S.

— А как ты догадался, что существует бесконечное множество А-чисел? — спросил Мак-Каллох.

— Ну, во-первых, — ответил Крейг, — надеюсь, ты не будешь возражать, что при любых числах X и Y, если число X порождает Y, то число 44X будет также порождать Y?

— Удачное наблюдение! — воскликнул Мак-Каллох. — Конечно, ты прав: ведь если X порождает Y, то число 4X порождает обращение числа Y, а значит, число 44X должно порождать обращение обращения Y — то есть само это число Y.

— Прекрасно, — продолжал Крейг. — Таким образом, если X порождает Y, то число 44X будет тоже порождать Y, и поэтому число 344X будет порождать ассоциат числа Y. Значит, 344 тоже представляет собой A-число. А раз 344 — это A-число, то число 3442344 должно также порождать само себя!

— Замечательно, — сказал Мак-Каллох, — теперь у нас есть уже два числа — 323 и 3442344, которые порождают сами себя. Но разве это позволяет нам сделать вывод о бесконечном множестве таких чисел?

— Видишь ли, — сказал Крейг, — если число S является A-числом, то A-числом должно быть также и число S44, поскольку для любых чисел X и Y, если X порождает Y, то число 44X тоже порождает Y, а значит, число S44X порождает ассоциат Y, поскольку S по условию есть A-число. Таким образом, A-числами являются такие числа, как 3, 344, 34444, и вообще A-числом является любое число, состоящее из тройки, за которой следует любое четное число четверок. Итак, число 323 порождает само себя; то же самое можно сказать о числах 3442344, 34444234444 и т. д. Следовательно, мы действительно имеем бесконечное множество решений.

— Но, между прочим, — добавил Крейг, — ведь существуют и другие решения. Например, числа 443 и 44443 тоже представляют собой A-числа. A-числом является также любое число, состоящее из четного числа четверок, тройки и опять четного числа четверок, как, например, число 4434444, — ведь для любого такого числа S число S2S порождает самое себя.

2. Одно из решений — это число 43243. В самом деле, поскольку число 243 порождает 43, то число 3243 порождает ассоциат числа 43. Значит, число 43243 должно порождать обращение ассоциата числа 43, другими словами, обращение числа 43243 (поскольку число 43243 — это ассоциат числа 43). Итак, число 43243 порождает обращение самого себя.

Здесь читатель может поинтересоваться, а как же все-таки было найдено само число 43243. Может, с помощью сравнения соответствующих относительных длин? Нет, для доказательства свойств, относящихся к нынешней машине, метод сравнения относительных длин оказывается слишком громоздким. Как будет показано в конце этой главы, решение было найдено именно с помощью принципа Крейга.

3. Одним из решений является число 3432343. Мы предоставляем читателю самому найти число, порождаемое числом 3432343, и убедиться, что оно действительно представляет собой ассоциат обращения числа 3432343. (Это решение также было найдено с помощью принципа Крейга.)

4. Подходит, например, число 53253. (Оно получено опять же с помощью принципа Крейга.)

5. Одно из решений — число 4532453.

6. Другое решение — это число 5432543.

7. Решение очевидно — в том, конечно, случае, если нам известно, что некое число порождает само себя. При этом если X порождает X, то ясно, что 5X порождает повторение X. Так, например, число 5323 порождает повторение числа 323.

8. Одно из решений — число 5332533. (Опять принцип Крейга!)

9. Одно из решений — число 3532353; оно тоже найдено с помощью принципа Крейга. (Надеюсь, я заинтриговал читателя этим принципом!)

10. 5(5) = 55. [Так как 5(5) — это повторение числа 5.] Поэтому возьмем число 5 в качестве M и число 5 в качестве X. (Ведь я не утверждал, что M и X должны быть разными числами.)

11. 4(4) = 4. [Поскольку 4(4) — это обращение числа 4, которое также равно 4.] Таким образом, M = 4 является одним из решений. (Фактически в качестве решения подойдет любая цепочка четверок.)

12. Возьмем M = 3 и А = 2. [3(2) = 222].

13. 4(6) = 6, а 6 = 4 + 2, поэтому 4(6) = 4 + 2. Итак, M = 4, а X = 2.

14. Одно из решений: M = 55, X = 55.

15. Одно из решений: M = 4, N = 44.

16. Одно из решений: M = 5, N = 55.

17. Одно из решений: M = 5, N = 4.

18. Одно из решений: M = 3, N = 5.

19. Одно из решений: M = 55, N = 45.

20. Пусть M — любое операционное число. Мы знаем (утверждение 1), что в случае любых чисел Y и Z, если Y порождает Z, MY порождает M(Z). Поэтому (принимая MY в качестве Z), если Y порождает MY, то MY должно порождать M(MY). Таким образом, если вы брать MY в качестве X, то число X будет порождать М(X). Итак, наша задача сводится к нахождению такого числа Y, которое порождает MY. Но эта задача уже была решена в предыдущей главе (с помощью закона Мак-Каллоха): надо просто взять в качестве Y число 32МЗ. Итак, за X мы принимаем число М32МЗ, причем это X будет порождать М(X). Проверим полученный результат: в самом деле, пусть X = М32МЗ. Но поскольку число 2МЗ порождает число МЗ, то число 32МЗ порождает число М32МЗ (согласно правилу 2), и, следовательно, число М32МЗ будет порождать М(М32МЗ). Таким образом, действительно X порождает М(X), где X — число М32МЗ.

Рассмотрим теперь некоторые приложения. Для того чтобы найти некое число X, порождающее повторение X, примем 5 в качестве М; тогда сразу получаем решение (а точнее, одно из решений) — число 53253. Для того чтобы найти число X, порождающее обращение самого себя, положим M = 4; тогда X есть число 43243. Для того чтобы найти число X, которое порождало бы ассоциат обращения X, выберем в качестве M число 34; отсюда возможное решение — число 3432343.

Для решения первой задачи Мак-Каллоха (найти число X, которое порождает повторение обращения ассоциата X) выберем в качестве M число 543 (5 — для получения повторения, 4 — для получения обращения и 3 — для получения ассоциата); решением в данном случае является число 543325433. (Читатель может легко удостовериться непосредственно, что число 543325433 действительно порождает повторение обращения ассоциата числа 543325433.)

Для решения второй задачи Мак-Каллоха (найти число X, которое порождает ассоциат повторения обращения X) возьмем в качестве M число 354; в результате получим решение — число 354323543.

Да, действительно, принцип Крейга великолепно работает в этих ситуациях!

21, 22, 23, 24. Задачи 21, 22 и 23 являются частными случаями задачи 24, поэтому мы начнем прямо с последней из них.

Пусть нам дано операционное число M и произвольное число А, причем мы хотим найти некое число X, которое порождает М(АХ). Вся штука теперь состоит в том, чтобы найти такое число Y, которое не порождает MY, однако порождает AMY. Возьмем в качестве Y число 32АМЗ. Поскольку Y порождает AMY, тогда MY в соответствии с утверждением 1 должно порождать M(AMY). Значит, если принять за X величину MY, то X будет порождать М(АХ). Но поскольку мы выбрали в качестве Y число 32АМЗ, то число X в (данном случае будет равно М32АМЗ. Итак, искомое решение — число вида М32АМЗ.

Попробуем применить этот результат к решению задачи 21. Прежде всего отметим, что число 7X7X — это просто повторение 7X, так что мы ищем некое число X, которое порождает повторение 7X — или повторение АХ, если считать А равным 7. Итак, А — это 7, а за M, очевидно, можно принять число 5 (поскольку 5 представляет собой операцию повторения); поэтому решением будет число 532753. (Читатель легко может убедиться сам, что число 532753 действительно порождает повторение числа 7532753.) Для задачи 22 в качестве А возьмем 9, а в качестве M примем 4, тогда решение — число 432943. Для задачи 23 в качестве А выберем 89, а в качестве M — число 3; решением будет 3328933.

25. Да, для любого числа А существует некое число X, которое порождает X⃖A, а именно 432A⃖443. (В данной конкретной задаче, для которой А = 67, имеем A⃖ = 76, так что решением будет число 4327643.)

26. При рассмотрении наиболее общего случая самое главное — понять, что X⃖A — это обращение A⃖Х, и по этому М(X⃖А) = М4(A⃖Х). Согласно второму принципу Крейга, числом X, порождающим М4(A⃖X), является число М432AМ43 — оно и будет решением дайной задачи. В частном случае, если вместо M взять 5, а вместо А — 67, числом X, порождающим повторение X⃖67, будет число 543276543 (в чем читатель может легко убедиться сам).

А сейчас мы перейдем к рассказу о еще более интересных событиях, связанных с машинами Мак-Каллоха. Недели две спустя Мак-Каллох получил от Крейга письмо следующего содержания:

Ответ Мак-Каллоха не заставил себя долго ждать:

Гости съехались. После превосходного обеда (его приготовила квартирная хозяйка Крейга миссис Хоффман) разговор зашел о математике.

— Я слышал, вы построили несколько логических машин, — сказал Мак-Каллох. — Интересно было узнать о них поподробнее. Может быть, вы расскажете, как они работают?

— О, это долгий разговор, — отвечал Фергюссон. — К тому же я до сих пор не нашел ответа на один очень важный вопрос, связанный с их работой. Может, вы с Крейгом зайдете как-нибудь ко мне в лабораторию? Тогда я вам обо всем и расскажу. А сегодня я предпочел бы поговорить о ваших машинах. Несколько дней назад я рассказывал Крейгу, что у них обнаружились некоторые свойства, о которых, мне кажется, вы и не подозреваете.

— Что же это за свойства? — спросил Мак-Каллох.

1. — Ну что ж, — сказал Фергюссон, — давайте начнем с конкретного вопроса, относящегося к вашей второй машине. Пусть имеются некие числа X и Y, такие, что число X порождает обращение числа Y, а Y порождает повторение числа X. Можете ли вы найти эти числа?

Крейга и Мак-Каллоха эта задача чрезвычайно заинтересовала, и они тут же засели за ее решение. Однако ни тому, ни другому это не удалось. Решить эту задачу, конечно, можно, и, вероятно, наш честолюбивый читатель не прочь попробовать сделать это сам. Заметим только, что в основе решения лежит один важный принцип (о котором пойдет речь в этой главе); если знать его, то решение задачи оказывается на удивление простым.

2. — Вы меня просто заинтриговали, — заявил Крейг, когда Фергюссон показал им решение. — Я вижу, что ваше решение правильно, но как вам удалось его найти? Вы просто случайно наткнулись на эти числа X и Y или действовали по заранее намеченному плану? Мне, например, это кажется прямо каким-то фокусом.

— Вот именно, — вставил Мак-Каллох. — Так, знаете, фокусник в цирке вытаскивает кролика из шляпы!

— Ага, — засмеялся Фергюссон, явно наслаждаясь произведенным эффектом. — Только не одного, а двух кроликов, и при том они еще некоторым образом влияют друг на друга. Это точно, — сказал Крейг. — Но все же мне бы хотелось знать, как вы догадались, каких именно кроликов надо тащить?

— Прекрасный, ну просто замечательный вопрос! — сияя, воскликнул Фергюссон. — А ну-ка — вот вам еще задачка: найти такие числа X и Y, чтобы число X порождало повторение числа Y, а число Y порождало обращение ассоциата X.

— С меня хватит! — воскликнул Мак-Каллох.

— Минуточку, минуточку, — перебил их Крейг. — Я, кажется, что-то начинаю понимать. Не хотите ли вы сказать, Фергюссон, что для любых двух операций, которые может выполнять машина, то есть для любых двух заданных операционных чисел M и N, должны существовать некие числа X и Y, характеризующиеся тем, что X порождает M(Y), а Y порождает N(X)?

— Вот именно! — воскликнул Фергюссон. — И поэтому мы можем найти, например, такие числа X и Y, для которых X порождает двойной ассоциат Y, а Y порождает повторение обращения X или любые другие комбинации, какие вы захотите.

— Вот так штука! — изумился Мак-Каллох. — Ведь все это время я пытался придумать машину как раз с таким свойством, а она у меня, оказывается, уже есть!

— Безусловно есть, — подтвердил Фергюссон.

— А как вы докажете это свойство? — спросил Мак-Каллох.

— Я бы хотел начать доказывать его постепенно, — ответил Фергюссон. — Собственно говоря, суть дела заключается в ваших правилах 1 и 2. Поэтому сначала позвольте сделать несколько замечаний относительно вашей первой машины — той, в которой используются только эти два правила. Начнем со следующей простой задачи: можно ли, используя правила 1 и 2, найти два различных числа X и Y, таких, чтобы число X порождало Y, а число Y в свою очередь порождало X?

Крейг и Мак-Каллох тут же занялись этой задачей.

— Ну, конечно, — рассмеялся вдруг Крейг. — Это же очевидно вытекает из того, что совсем недавно показы вал мне Мак-Каллох.

А вы можете найти эти числа?

— Теперь, — сказал Фергюссон, — для любого числа А существуют такие числа X и Y, что X порождает Y, а число Y порождает АХ. Если число А нам задано, то можете ли вы найти числа X и Y? Например, можете ли вы найти такие X и Y, чтобы X порождало Y, а Y порождало 7X?

— Мы все еще пользуемся только правилами 1 и 2 или уже можно применять правила 3 и 4? — спросил Крейг.

— Вам понадобятся только правила 1 и 2, — ответил Фергюссон.

— Я уже нашел решение! — тут же заявил Крейг.

4. — Интересно, — сказал Мак-Каллох, просмотрев решение Крейга. — А у меня решение другое.

Действительно, в этой задаче существует и второе решение. Можете ли вы его найти?

5. — Ну, а теперь, — сказал Фергюссон, — мы добрались до действительно важного свойства. Так, из одних только правил 1 и 2 следует, что для любых чисел А и В существуют такие числа X и Y, при которых X порождает AY, а Y порождает BX. Например, существуют такие X и Y, что X порождает 7Y, а Y порождает 8X. Не можете ли вы найти эти числа?

6. — Из последней задачи, — сказал Фергюссон, — со всей очевидностью следует (правда, из второго принципа Крейга это получается еще более просто), что для любых операционных чисел M и N должны существовать такие числа X и Y, при которых X порождает M(Y), а Y порождает N(X). Причем это оказывается справедливым не только для данной машины, но и для любой машины, в программу работы которой включены правила 1 и 2. С помощью вашей теперешней машины можно, например, найти такие X и Y, при которых число X порождает обращение числа Y, а число Y порождает ассоциат числа X. Сумеете ли вы их найти?

7. — Это страшно интересно, — сказал Фергюссону Мак-Каллох, когда они с Крейгом решили последнюю задачу. — Но у меня возник вот какой вопрос: подчиняется ли моя машина «двойному» аналогу второго принципа Крейга? Иначе говоря, если заданы два операционных числа M и N, а также два произвольных числа А и В, то обязательно ли существуют такие числа X и Y, при которых X порождает M(AY), а Y порождает N(BX)?

— Ну, конечно, — подтвердил Фергюссон. — Например, существуют такие числа X и Y, при которых число X порождает повторение 7Y, а число Y порождает обращение 89X.

Не могли бы вы найти эти числа?

8. — Я подумал еще вот о чем, — сказал Крейг. — Если имеется некоторое операционное число M и произвольное число В, то обязательно ли должны существовать такие числа X и Y, при которых X порождает М(Y), а Y порождает BX? Например, существуют ли такие X и Y, при которых число X порождает ассоциат Y, а число Y порождает число 78X?

А как думаете вы?

9. — Фактически, — продолжал пояснения Фергюссон, — у нас возможны самые разные комбинации. Так, давая некоторые операционные числа M и N и произвольные числа А и В, всегда можно найти числа X и Y, которые отвечают любому из ниже перечисленных условий:

а) X порождает М(АY) а Y порождает N(X);

б) X порождает М(АY) а Y порождает BX;

в) X порождает M(Y), а Y порождает X;

г) X порождает M(AY), а Y порождает X.

Попробуйте доказать эти утверждения.

10. Триплеты и так далее.

— Ну, теперь-то, мне кажется, мы перебрали уже все возможные варианты, — сказал Крейг.

— Да нет, — ответил Фергюссон. — То, что я вам показывал до сих пор, — это еще только начало. А знаете ли вы, например, что существуют три числа X, Y и Z, такие, что число X порождает обращение Y, число Y порождает повторение Z, а число Z порождает ассоциат X?

— Неужели? — удивился Мак-Каллох.

— Именно так, — подтвердил Фергюссон. — Более того, если заданы три произвольных операционных числа M, N и P, то должны существовать такие числа X, Y и Z, при которых X порождает M(Y), Y порождает N(Z), a Z порождает P(X).

Не сумеете ли вы, читатель, доказать это утверждение? И в частности, каковы будут эти числа X, Y и Z, если известно, что число X порождает обращение Y, число Y порождает повторение Z, а число Z порождает ассоциат X?

После того как Крейг и Мак-Каллох решили и эту задачу, Фергюссон сказал:

— Конечно, тут тоже возможны самые разные варианты этого «тройного» закона. Например, если заданы три любых операционных числа M, N и P, а также три произвольных числа А, В и С, то существуют такие числа X, Y и Z, при которых число X порождает M(AY), число Y порождает N(BZ), а число Z порождает P(СХ). Это справедливо и в том случае, если взять не три числа А, В, С, а любые два из них или даже одно.[5] Так, мы можем найти такие числа X, Y и Z, при которых X порождает АY, Y порождает M(Z), a Z порождает N(BX). Возможны, естественно, и всякие другие варианты — вы вполне можете заняться ими на досуге.

— Кроме того, — продолжал он, — та же идея действует и тогда, когда мы используем 4 операционных числа или даже более. Например, мы можем найти числа X, Y, Z и W, при которых число X порождает 78Y, число Y порождает повторение Z, число Z порождает обращение W, а число W порождает ассоциат 62X. Возможности практически бесконечны, причем их удивительное многообразие обусловлено всего лишь правилами 1 и 2.

Решения

1. Одно из решений состоит в том, чтобы принять X = 4325243 и Y = 524325243. Поскольку число 25243 порождает число 5243, то число 325243 порождает ассоциат 5243, или число 524325243, которое и есть Y.

Далее, так как число 325243 порождает Y, то число 4325243 порождает обращение Y, но 4325243 — это как раз и есть X. Таким образом, X порождает обращение Y. Кроме того. Y, очевидно, порождает повторение X (потому что Y — это есть число 52X, а поскольку число 2X порождает X, то число 52X будет порождать повторение X). Итак, X порождает обращение Y, а Y порождает повторение X.

2. Крейг воспользовался законом Мак-Каллоха, а именно: для любого числа А существует некоторое число X (а именно число 32A3), которое порождает число АХ. Так, в частности, если мы примем А за число 2, то получим некоторое число X (а именно число 3223), которое порождает 2X. Число же 2X в свою очередь будет порождать X. Таким образом, в качестве решения этой задачи подходит пара чисел 3223 и 23223: 3223 порождает 23223, а 23223 порождает 3223.

3. Крейг решил эту задачу следующим способом. Он рассудил, что ему надо всего лишь найти такое число X, которое порождает 27X. Тогда, положив Y = 27X, мы получим, что число X порождает Y, а число Y порождает 7X. Такое число X он тоже нашел — это число 32273. Поэтому решение Крейга имеет вид: X = 32273, Y = 2732273.

То же самое происходит, конечно, и в том случае, если вместо конкретного числа 7 мы возьмем любое число А. В самом деле, если X = 322АЗ, а Y = 2A322АЗ, то число X будет порождать Y, а число Y будет порождать АХ.

4. Что же касается Мак-Каллоха, то он подошел к решению данной задачи несколько иначе. Он начал с того, что стал искать такое число Y, которое порождает 72Y. Теперь, если обозначить через X число 2Y, то мы получаем, что число X порождает Y, а число Y порождает 7X. При этом нам уже известно, как найти такое число Y — надо взять Y = 32723. Итак, решение Мак-Каллоха имеет вид: X = 232723, Y = 32723.

5. Единственное, что нам нужно — это найти такое число X, которое порождало бы число А2ВХ. Тогда, если мы положим Y = 2ВХ, то будем иметь, что число X порождает АY, а число Y порождает BX. Таким числом X, которое порождает А2ВХ, является число 32А2ВЗ. Стало быть, решение задачи выглядит так: X = 32A2ВЗ, Y = 2B32A2ВЗ. (В частном случае А = 7, В = 8 и решением будет X = 327283, Y = 28327283.)

6. Сначала попробуем решить эту задачу с помощью второго принципа Крейга, который, как мы помним, гласит, что для любого операционного числа M и для произвольного числа А существует некоторое число X (а именно число М32АМЗ), которое порождает М(АХ). Возьмем теперь два любых операционных числа M и N. Тогда, согласно этому принципу (если взять в качестве А число N2), найдется некое число X (а именно число M32N2M3), которое порождает число M(N2X). Ясно также, что число N2X порождает N(X). Поэтому если обозначить число N2X через Y, то мы получим, что число X порождает М(Y), а число Y порождает N(X). Следовательно, решение задачи имеет вид: X = M32N2M3, Y = N2M32N2M3. (Для конкретной задачи, предложенной Фергюссоном, положим M = 4 и N = 3, тогда решение будет таким: X = 4323243, Y = 324323243, читатель сам может убедиться в том, что X порождает обращение Y, а Y порождает ассоциат X; последняя часть этого утверждения особенно очевидна.)

Можно подойти к решению этой задачи и по-другому. Из решения задачи 5 мы знаем, что существуют числа Z и W, при которых Z порождает NW, a W порождает MZ (а именно числа Z = 32N2M3 и W = 2M32N2M3). Тогда, согласно утверждению 1 из предыдущей главы, число MZ порождает M(NW), a число NW порождает N(MZ). Поэтому если мы обозначим MZ через X, a NW через Y, то сразу получим, что число X порождает М(Y), а число Y порождает N(X). Таким образом, мы получаем то же самое решение: X = M32N2M3 и Y = N2M32N2M3.

7. Здесь нам необходимо найти такое число X, которое порождало бы число М(AN2BX); согласно второму принципу Крейга, таким числом X является число M32AN2BM3. Возьмем N2BX в качестве Y; тогда число X порождает М(AY), а число Y (которое есть N2BX), очевидно, порождает N(BX). Итак, общее решение задачи (или, по крайней мере, одно из возможных общих решений) имеет вид: X = M32AN2BM3, Y = N2BM32AN2BM3. Для конкретного частного случая положим M = 5, N = 4, А = 7 и В = 89.

8. Согласно второму принципу Крейга, существует некоторое число X, которое порождает М(2ВХ), а именно X = М322ВМЗ. Положим теперь Y = 2ВХ. Тогда X порождает М(Y), а Y порождает BX. Для конкретного частного случая примем M = 3 и В = 78; при этом решение будет иметь вид: X = 33227833, Y = 27833227833.

9. а) Возьмем некоторое число X, которое порождает M(AN2X), и обозначим через Y число N2X. (Мы можем взять X равным M32AN23, a Y = N2M32AN23.) Тогда X порождает М(AY), а Y порождает N(X).

б) Теперь возьмем X, которое порождает М(А2ВХ), и обозначим через Y число 2ВХ. (Итак, в этом случае решение имеет вид: X = М32А2ВЗ, Y = 2ВМ32А2ВЗ.)

в) Если число X порождает М(Y), а Y = 2X, то мы сразу имеем решение задачи; поэтому положим X = М322МЗ, Y = 2М322МЗ.

г) Если X порождает М(AY), а Y = 2X, то мы сразу получаем требуемое решение; поэтому положим X = М32А2МЗ и Y = 2М32А2МЗ.

10. Согласно второму принципу Крейга, существует некое число X, которое порождает M(N2P2X), a именно X = M32N2P2M3. Положим Y = N2P2X, тогда число X порождает М(Y). Пусть теперь Z = P2X, тогда Y = N2Z; при этом число Y порождает N(Z), а число Z порождает P(X). Таким образом, в явном виде решение будет таким: X = M32N2P2M3, Y = N2P2M32N2P2M3, Z = P2M32N2P2M3.

Для частного случая это решение имеет вид: X = 432523243, Y = 5232432523243, Z = 32432523243.

Читатель сам может легко убедиться, что действительно X порождает обращение Y, Y порождает повторение Z, a Z порождает ассоциат X.

Кстати говоря, для любых трех чисел А, В и С мы всегда можем найти такие числа U, V и W, при которых U порождает AV, V порождает BW, a W порождает CU. Для этого надо просто взять такое число U, которое порождало бы число А2В2СU (если же мы воспользуемся вторым принципом Крейга, то получим U = 32A2B2C3). Положим теперь V = 2B2CU и W = 2CU. Тогда число U будет порождать AV, число V будет порождать BW, а число W будет порождать CU. Наконец, если теперь принять А, В и С за операционные числа и положить X = AV, Y = BW и Z = CU, то мы получим, что число X порождает A(Y), число Y порождает B(Z), а число Z порождает С(X). Таким образом, мы нашли еще один способ решения данной задачи.

Два дня спустя полицейское начальство из Скотланд-Ярда внезапно и совершенно неожиданно для Крейга срочно откомандировало его в Норвегию для расследования, хотя и интересного, но нас не касающегося. Поэтому я воспользуюсь отсутствием Крейга, чтобы поделиться с вами кое-какими собственными соображениями по поводу числовых машин Мак-Каллоха. Те же читатели, которым не терпится узнать решение загадки сейфа из Монте-Карло, могут отложить чтение этой главы на потом.

Математики обожают обобщать! Сплошь и рядом случается так: некий математик по имени X доказывает новую теорему и публикует доказательство в научном журнале. Потом проходит полгода и появляется другой математик, Y, который вдруг заявляет: «Ну ладно, неплохую теоремку доказал этот X, однако я могу доказать гораздо более общий случай!» И тут же печатает статью под названием «Об одном обобщении теоремы X-а». Или же Y оказывается похитрее и поступает следующим образом: сначала он втайне обобщает теорему, доказанную X-м, а потом исследует какой-нибудь частный случай своего обобщения. Этот частный случай по внешнему виду обычно настолько отличается от исходной теоремы, предложенной X-м, что Y вполне может опубликовать полученный результат в качестве новой, оригинальной теоремы. Тут на сцене, естественно, появляется третий математик по имени Z: этого Z никак не оставляет чувство, что где-то теоремы X-а и Y-a в чем-то важном очень сходны. Он начинает напряженно работать и… обнаруживает некий общий принцип. Z тут же публикует работу, в которой формулирует и доказывает этот новый общий принцип, а в заключение добавляет: «Теоремы, предложенные X-м и Y-м, вполне могут рассматриваться как частные случаи нашего общего принципа, поскольку…»

Ну что ж, я тут не исключение. Поэтому я хочу сначала указать на некоторые свойства машин Мак-Каллоха, которых, как мне кажется, не заметили ни сам Мак-Каллох, ни Крейг, ни Фергюссон, после чего я попытаюсь сделать некоторые обобщения.

Первое, что больше всего поразило меня при нашем обсуждении работы второй машины Мак-Каллоха, было то, что после введения правила 4 (правило повторения) мы уже больше не нуждаемся в правиле 2 (правило ассоциата) для того, чтобы получить принцип Крейга и законы Фергюссона! В самом деле, рассмотрим машину, в которой используются только правила 1 и 4. Для такой машины мы всегда можем найти некое число X, которое порождает само себя; можем также найти такое число, которое порождает повторение самого себя; задавая произвольное число А, мы можем найти такое число X, которое порождает АХ; наконец, мы можем найти число X, которое порождает повторение числа АХ или же повторение повторения АХ. Кроме того, используя машину Мак-Каллоха, из которой выведено правило 2, мы можем найти такое число X, которое порождает обращение самого себя, или число X, которое порождает повторение своего собственного обращения, или же число X, которое порождает обращение числа АХ, или, наконец, число X, которое порождает повторение обращения числа АХ. Далее, рассмотрим машину, в которой используются предложенные Мак-Каллохом правила 1, 2 и 4 (за исключением правила 3, то есть правила обращения). При такой машине у нас имеются два различных способа построения числа, которое порождает ассоциат самого себя, два способа построения числа, которое порождает свое собственное повторение; наконец, два способа построения числа, порождающего ассоциат своего повторения или повторение ассоциата самого себя.

Наконец, если у нас имеется произвольная машина, в которую заложены лишь правила 1 и 4, то принцип Крейга и законы Фергюссона продолжают выполняться и в этом случае. Таким образом, если бы мы вместо правила 2 воспользовались правилом 4, то для большинства задач, о которых шла речь в двух предыдущих главах, мы вполне могли бы получить альтернативные решения. (Понятно ли читателю, как все это можно сделать? Если нет, то можно обратиться к приведенным далее пояснениям.)

Я мог бы рассказать еще о многом, но лучше, пожалуй, будет сформулировать мои основные замечания в виде трех теорем.

Теорема 1. Закон Мак-Каллоха (который, как известно, гласит, что при любом А существует некое число X, которое порождает число АХ) оказывается справедливым не только для машин, подчиняющихся правилам 1 и 2, но и для машин, подчиняющихся правилам 1 и 4.

Теорема 2. Любая машина, которая подчиняется закону Мак-Каллоха, подчиняется также и двум принципам Крейга.

Теорема 3. Любая машина, которая подчиняется одновременно второму принципу Крейга и правилу 1, должна подчиняться также и всем законам Фергюссона.

Не сообразит ли читатель, как доказать все эти теоремы?

Решения

Рассмотрим сначала произвольную машину, которая подчиняется правилам 1 и 4. Как известно, при любом X число 52X порождает число XX; поэтому если выбрать в качестве X число 52, то мы получим, что число 5252 порождает число 5252. Итак, у нас есть число, которое порождает само себя. Кроме того, число 552552 порождает повторение самого себя. Далее, чтобы для любого А найти число X, которое порождает АХ, возьмем в качестве X число 52А52 (в самом деле, оно порождает повторение числа А52, которое есть число A52A52, то есть число АХ). Тем самым мы доказали теорему 1. (Если мы хотим найти число X, которое порождает повторение АХ, то в качестве X следует взять число 552А552.)

А теперь рассмотрим машину, которая подчиняется выведенным Мак-Каллохом правилам 1, 3 и 4. Числом, порождающим обращение самого себя, является, например, число 452452 (оно порождает обращение повторения числа 452, или, другими словами, обращение числа 452452). (Сравните его с предыдущим решением 43243.) Числом, которое порождает повторение обращения самого себя, является число 54525452. (Сравните его с прежним решением 5432543.)

Далее, рассмотрим машину, которая подчиняется правилам 1, 2 и 4. Мы знаем, что число 33233 порождает свой собственный ассоциат точно так же, как и число 352352. Что касается числа X, порождающего повторение самого себя, то у нас уже имеются два решения — это числа 35235 и 552552. Что же касается числа X, порождающего ассоциат повторения самого себя, то одним решением служит число 3532353; другим — число 35523552. Наконец, для числа, которое порождает повторение своего собственного ассоциата, также существуют два решения — это число 5332533 или число 53525352.

Наконец, рассмотрим некоторую произвольную машину, которая подчиняется по меньшей мере двум из правил Мак-Каллоха, а именно: правилам 1 и 4. Для заданного операционного числа M числом А, порождающим М(X), оказывается число М52М52. (Сравните его с прежним решением — числом М32МЗ, полученным для машины, в которой вместо правила 4 используется правило 2.) Если теперь задано операционное число M и некое число А, то числом X, порождающим M(AX), будет число М52АМ52. (Сравните его с прежним решением — М32АМЗ.) Построенные решения показывают нам, что оба принципа Крейга могут быть получены на основании правил 1 и 4. Впрочем, я сформулировал гораздо более общее утверждение, а именно: для того чтобы получить принципы Крейга, достаточно одного только закона Мак-Каллоха (теорема 2). Это утверждение можно доказать тем же способом, который использовался нами в гл. 10. В самом деле, для любого заданного операционного числа M существует некое число Y, которое порождает MY; отсюда ясно, что число MY порождает М(МY). Поэтому число X порождает М(X), где X = MY. Точно так же для любого числа А, если имеется некоторое число Y, порождающее AMY, число MY порождает М(АMY) и, следовательно, число X порождает М(АХ) при X = MY.

Что же касается теоремы 3, то ее можно доказать так же, как это делалось в предыдущей главе. [Например, если даны операционные числа M и N и если выполняется второй принцип Крейга, то существует некое число X, которое порождает M(N2X). Если теперь мы обозначим число N2X через Y, то получим, что число X порождает М(Y), а число Y порождает N(X).]

Дело, по которому Крейг поехал в Норвегию, заняло у него гораздо меньше времени, чем он предполагал, и ровно через три недели инспектор возвратился домой. Дома его ждала записка от Мак-Каллоха:

— Вот и отлично! — сказал себе Крейг. — Я вернулся как раз вовремя!

Крейг приехал к Мак-Каллоху минут через пятнадцать после того, как там появился Фергюссон.

— С благополучным возвращением! — приветствовал приятеля Мак-Каллох.

— Пока вас не было, — сразу же сообщил Фергюссон, — Мак-Каллох изобрел новую числовую машину!

— Ну да? — удивился Крейг.

— Я занимался этим не один, — сказал Мак-Каллох, — Фергюссон тоже приложил к ней руку. А вообще-то машина интересная; на этот раз в нее введены следующие четыре правила:

правило MI: для любого числа X число 2X2 порождает X;

правил о МII: если число X порождает число Y, то число 6X порождает число 2Y;

правило MIII: если число X порождает число Y, то число 4X порождает число Y⃖ (как и в случае предыдущей машины);

правило MIV: если число X порождает число Y, то число 5X порождает число YY (как и в случае предыдущей машины).

— Эта машина, — продолжал Мак-Каллох, — обладает всеми прекрасными свойствами моей последней машины — она подчиняется двум твоим принципам и, кроме того, закону двойных аналогов Фергюссона.

Крейг довольно долго и внимательно изучал эти правила. Наконец он сказал:

— Что-то мне никак не удается сдвинуться с места. Не могу даже найти число, которое порождает само себя. Есть тут такие числа?

— Есть, — ответил Мак-Каллох, — но с помощью этой машины найти их гораздо труднее, чем в предыдущем случае. Честно говоря, я тоже не смог решить эту задачу. А вот Фергюссон с ней справился. Более того, теперь мы знаем, что такое короткое число, порождающее само себя, состоит из десяти цифр.

Крейг опять глубоко задумался.

— А что, первых двух правил недостаточно для нахождения такого числа? — поинтересовался он наконец.

— Нет, конечно! — ответил Мак-Каллох. — Для получения этого числа нам необходимы все четыре правила.

— Удивительное дело, — пробормотал Крейг и вновь погрузился в глубокое раздумье.

— О господи! — вдруг воскликнул он, буквально подскочив на стуле. — Да ведь это же решение загадки сейфа!

— О чем это вы? — спросил Фергюссон.

— А-а, прошу прощения! Вы ведь не знаете, — сказал Крейг и поведал им всю историю с банковским сейфом из Монте-Карло.

— Надеюсь, вы понимаете, что наш разговор сугубо конфиденциальный, — заключил свой рассказ Крейг. — А теперь, Мак-Каллох, если ты дашь мне число, которое порождает само себя, то я сразу же смогу назвать комбинацию, которая откроет замок сейфа.

Итак, читателю предлагаются три задачи.

1) Какое число X порождает само себя в последней машине?

2) Какая комбинация открывает замок сейфа?

3) Как связаны между собой первые два вопроса?

Рано утром следующего дня Крейг, подыскав надежного человека, отправил в Монте-Карло пакет, адресованный Мартинесу, в котором была записана найденная им накануне кодовая комбинация. Курьер прибыл вовремя, и сейф был благополучно открыт.

Как и обещал Мартинес, совет директоров банка прислал Крейгу солидное денежное вознаграждение. Крейг настоял на том, чтобы разделить эти деньги с Мак-Каллохом и Фергюссоном. Свой успех трое друзей решили отпраздновать, заказав шикарный ужин в ресторане «У льва».

— А знаете, — сказал Крейг, отведав превосходного хереса. — Пожалуй, это было одно из самых интересных дел в моей практике. Подумать только, числовые машины, созданные из чисто интеллектуального любопытства, и вдруг оказывают такую неоценимую помощь на практике!

Решения

Сначала еще несколько слов о загадке сейфа из Монте-Карло. В последнем условии Фаркуса не говорится, что требуемая комбинация у непременно должна отличаться от комбинации x. Поэтому если предположить, что х и у представляют собой одну и ту же комбинацию, то указанное условие можно будет прочитать так: «Пусть комбинация х родственна по отношению к комбинации х, тогда если комбинация х блокирует замок, то комбинация х будет нейтральной; если же комбинация х оказывается нейтральной, то комбинация х блокирует замок». Однако невозможно, чтобы комбинация х одновременно была нейтральной и блокировала замок. Следовательно, если комбинация х родственна но отношению к х, тогда эта комбинация не может ни оказаться нейтральной, ни блокировать замок. А значит, она должна этот замок открывать! Таким образом, если мы сумеем найти комбинацию х, которая родственна самой себе, то такая комбинация х обязательно откроет нам замок.

Конечно, Крейг понял это еще задолго до того, как вернулся в Лондон. Но как найти комбинацию х, которая родственна самой себе? Именно на этот вопрос Крейг и не мог ответить до тех пор, пока судьба не столкнула его с третьей машиной Мак-Каллоха.

Оказывается, задача нахождения комбинации, которая, согласно условию Фаркуса, является родственной самой себе, по своей сути тождественна задаче нахождения числа, которое порождает само себя в последней машине Мак-Каллоха. Единственное существенное отличие заключается в том, что кодовые комбинации для замка — это цепочки букв, тогда как числовые машины работают с цепочками цифр. Однако первую задачу можно легко преобразовать ко второй, и наоборот, следующим простым приемом.

Во-первых, мы рассматриваем лишь комбинации из букв Q, L, V, R (совершенно очевидно, что только эти буквы играют в задаче существенную роль). Предположим теперь, что вместо этих букв мы будем использовать собственно цифры 2, 6, 4, 5 (то есть 2 вместо Q, 6 вместо L, 4 вместо V и 5 вместо R). Для удобства запишем это так:

Теперь посмотрим, какой вид примут первые четыре условия Фаркуса, если мы запишем их не в буквах, а в цифрах.

(1). Для любого числа X число 2X2 является родственным числу X.

(2). Если число X родственно числу Y, то число 6X оказывается родственным числу 2Y.

(3). Если число X родственно числу Y, то число 4X родственно числу Y⃖.

(4). Если число X родственно числу Y, то число 5X родственно числу YY.

Сразу видно, что это — точно те же правила, которым подчиняется последняя машина Мак-Каллоха, с той лишь разницей, что вместо слова «порождает» используется слово «родственно». (Конечно, я мог бы воспользоваться словом «порождает» и в гл. 8, где речь шла об условиях Фаркуса, но тогда читателю было бы слишком уж легко обо всем догадаться!)

Позвольте мне сказать это еще раз и поточнее. Для любой комбинации х, состоящей из букв Q, L, V, R, мы будем обозначать через х число, которое получается при замене Q на цифру 2, L на цифру 6, V на цифру 4 и R на цифру 5. Например, если это комбинация вида VQRLQ, то х — число 42562. При этом мы будем называть число х кодовым номером комбинации х. (Кстати, идея приписывания логическим высказываниям специальных чисел — так называемых «гёделевых номеров» — принадлежит известному логику Курту Гёделю и известна под названием гёделевой нумерации. Она очень важна, как мы увидим в IV части нашей книги.)

Значит, мы можем окончательно сформулировать главную мысль последнего абзаца в таком виде: для любых комбинаций х и у, составленных из четырех букв Q, L, V, R, если, исходя из правил MI, MII, MIII и MIV, используемых в последней машине Мак-Каллоха, можно показать, что число х порождает число у, то тогда, исходя из первых четырех условий Фаркуса, можно показать и то, что комбинация х является родственной по отношению к комбинации у, и наоборот.

Таким образом, если мы находим число, которое должно порождать само себя в последней числовой машине Мак-Каллоха, то это число должно оказаться кодовым номером некой комбинации, родственной самой себе, причем эта комбинация будет открывать замок.

Но как же нам найти такое число N, которое, порождало бы само себя в нашей последней машине? Прежде всего будем искать некоторое число Н, такое, чтобы для любых чисел X и Y, если число X порождает число Y, число НХ порождало бы число Y2Y2. Если мы сумеем найти это число Н, тогда при любом Y число Н2Y2 будет порождать число Y2Y2 (потому что, согласно правилу MI, число 2Y2 порождает число Y), а значит, число Н2Н2 будет порождать число Н2Н2; тем самым мы получим искомое число N. Но как найти число Н?

Эта задача сводится к следующей: как, исходя из заданного числа Y и последовательно применяя операции, которые способна выполнять наша машина, получить число Y2Y2? Так вот, построить число Y2Y2 из числа Y можно следующим способом: сначала построить обращение числа Y, получив число Y⃖; затем слева от Y⃖ приписать цифру 2, получив тем самым число 2Y⃖; далее построить обращение числа 2Y⃖, получив число Y2; наконец, построить повторение числа Y2, получив число Y2Y2. Эти операции обозначаются соответственно операционными числами 4, 6, 4 и 5, поэтому в качестве Н мы выберем число 5464.

Давайте проверим, подходит ли нам найденное число Н. Пусть число X порождает число Y; тогда мы должны выяснить, действительно ли число 5464Н порождает число Y2Y2. Но поскольку X порождает Y, то число 4X порождает число Y⃖ (в соответствии с правилом MIII); значит, число 64X порождает число 2Y⃖ (в соответствии с правилом МII). Отсюда следует, что число 464X порождает число Y2 (в соответствии с правилом MIII), и, стало быть, число 5464X порождает число Y2Y2 (в соответствии с правилом MIV). Итак, мы получили, что если X порождает Y, то число НХ в самом деле порождает число Y2Y2.

Теперь, когда число Я найдено, выберем число N равным Н2Н2, в результате мы получим число 5464254642, которое порождает само себя. (Читатель может легко убедиться в этом самостоятельно.)

Но раз число 5464254642 порождает само себя, то, значит, это и есть кодовый номер той комбинации, которая открывает замок сейфа. Ясно, что указанная комбинация имеет вид RVLVQRVLVQ.

Конечно, задачу о сейфе из Монте-Карло можно решить и не преобразовывая ее в задачу для числовой машины, однако я привел здесь это решение по двум причинам. Во-первых, именно так решал во времени эту задачу сам Крейг, а во-вторых, я подумал, что читателю будет интересно увидеть, как две математические задачи могут иметь разное содержание, но одну и ту же абстрактную форму.

Для того чтобы непосредственно убедиться в том, что комбинация RVLVQRVLVQ является родственной по отношению к самой себе (а значит, и открывает замок), будем рассуждать следующим образом. Комбинация QRVLVQ родственна по отношению к комбинации RVLV (согласно свойству Q), поэтому комбинация VQRVLVQ будет родственной по отношению к обращению комбинации RVLV (согласно свойству V), то есть к комбинации VLVR. Значит, комбинация LVQRVLVQ родственна по отношению к комбинации QVLVR (согласно свойству L), и, следовательно, комбинация VLVQRVLVQ оказывается родственной по отношению к обращению комбинации QVLVR, то есть комбинации RVLVQ. Тогда (согласно свойству R) комбинация RVLVQRVLVQ будет родственной по отношению к повторению комбинации RVLVQ, то есть к комбинации RVLVQRVLVQ. Итак, комбинация RVLVQRVLVQ действительно является родственной самой себе.