Гл. 10-11.

10 Принцип Крейга

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

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

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

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

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

первое из моих новых правил.

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

Стр. 125

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

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

Прекрасно. А теперь возьмем число X, которое порождает число 7695, а именно число 27695, потом введем в машину число 427695 и посмотрим, что

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

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

машина может проделывать с помощью правила 3, конечно, в совокупности с правилами 1 и 2.

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

правило 3, а использовались лишь правила 1 и 2,— число 323 было единственным числом, которое могло порождать самое себя. Для моей теперешней машины

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

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

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

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

Стр. 126

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

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

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

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

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

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

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

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

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

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

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

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

Стр. 127

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

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

Операционные числа

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

массу других!

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

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

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

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

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

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

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

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

Стр. 128

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

Пусть теперь имеются определенные числа — а фактически любые числа, составленные из цифр 3, 4 или S,— я их буду называть операционными числами, поскольку они определяют операции, которые может выполнять твоя машина. Пусть М—некоторое число, состоящее из цифр 3, 4 или 5, и пусть F—произвольная операция. Я буду говорить, что число М определяет операцию F, имея в виду, что для любых двух чисел X

и У, в случае если X порождает У, число М(Х) порождает число F(Y). Например, если число X порождает число У, то число 4Х порождает обращение числа

У (согласно правилу 3), и поэтому я буду говорить, что число 4 определяет или обозначает операцию обращения данного числа. Аналогичным образом в соответствии с правилом 4 число 5 определяет операцию повторения, а число 3 — операцию ассоциации, то есть операцию получения ассоциата данного числа. Далее, предположим, что F представляет собой операцию, которая, если ее выполнить над числом X, дает нам ассоциат повторения X. Другими словами, F(X) есть ассоциат повторения числа X. Существует ли число М,

Стр. 129

которое описывает эту операцию, и если да, то что это за число?

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

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

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

существовать операционные числа М и N, такие, что при М, не равном N, операция М оказывается тождественной операции N?

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

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

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

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

само X. Правда, я не знаю, как назвать такую операцию, которая при воздействии на число X дает нам само это число.

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

Стр. 130

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

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

А теперь,— пояснил далее Крейг,— если нам заданно операционное число М и произвольное число X, то, чтобы обозначить результат воздействия операции

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

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

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

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

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

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

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

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

Стр. 131

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

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

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

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

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

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

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

17. Не могли бы вы отыскать два операционных числа М и N, для которых

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

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

Принцип Крейга

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

Ну, конечно, — отвечал Крейг.— Теперь, я думаю, ты легко сможешь понять идею этого принципа

Стр. 132

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

Более того,— продолжал Крейг,—если задано какое-то операционное число М, то существует очень простой способ найти такое X, которое порождает

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

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

Сейчас объясню,— ответил Крейг,— но сначала давай разберем поподробнее одно вполне элементарное обстоятельство, а именно: для любого операционного

числа М и для любых чисел У и Z, если число У порождает число Z, то МУ порождает M(Z). Например

Стр. 133

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

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

- Прекрасно,— сказал Крейг,— однако этот факт легко забывается, поэтому разреши мне повторить его еще раз, с тем чтобы он хорошенько отложился у тебя в голове. Итак, утверждение 1: для любого операционного числа М и для любых чисел У и Z, если число У порождает число Z, число МУ порождает число M(Z). В частности, число M2Z порождает число M(Z).

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

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

Стр. 134

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

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

Некоторые варианты принципа Крейга

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

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

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

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

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

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

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

Стр. 135

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

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

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

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

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

Стр. 136

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

Решени

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

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

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

обязательно должно порождать само себя, поскольку

число S2S порождает ассоциат числа S, который и есть S2S.

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

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

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

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

Стр. 137

А-число. А раз 344—это А-число, то число 3442344 должно также порождать само себя!

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

сделать вывод о бесконечном множестве таких чисел?

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

за которой следует любое четное число четверок. Итак, число 323 порождает само себя; то же самое можно сказать о числах 3442344, 34444234444 и т. д. Следовательно, мы действительно имеем бесконечное множество решений.

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

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

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

Стр. 138

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

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

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

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

7. Решение очевидно — в том, конечно, случае, если нам

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

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

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

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

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

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

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

Стр. 139

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

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

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

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

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

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

20. Пусть М—любое операционное число. Мы знаем (утверждение 1), что в случае любых чисел Y и Z, если У порождает Z, MY порождает M(Z). Поэтому (принимая MY в качестве Z), если У порождает MY, то MY должно порождать M(MY). Таким образом, если вы брать МУ в качестве X, то число X будет порождать

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

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

Стр. 140

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

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

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

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

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

Стр. 141

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

так что решением будет число 4327643.)

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

11 Законы Фергюссона

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

Мой дорогой Мак-Каллох!

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

Стр. 142

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

В следующую пятницу я пригласил Фергюссона пообедать со мной. Не хочешь ли присоединиться к нам? Уверен, что у вас обоих найдется много общих тем для разговора; быть может, мы узнаем, что у него на уме.

В надежде на скорую встречу искренне твой

Л. Крей

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

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

С глубоким уважением

Н. Мак-Каллох

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

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

Стр. 143

узнать о них поподробнее. Может быть, вы расскажете, как они работают?

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

и не подозреваете.

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

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

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

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

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

Стр. 144

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

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

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

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

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

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

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

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

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

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

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

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

Стр. 145

можете ли вы найти числа X и У? Например, можете ли вы найти такие X и У, чтобы X порождало У, а У порождало 7X7

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

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

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

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

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

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

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

Сумеете ли вы их найти?

7.— Это страшно интересно,— сказал Фергюссону Мак-Каллох, когда они с Крейгом решили последнюю задачу.— Но у меня возник вот какой вопрос: подчиняется ли моя машина «двойному» аналогу второго принципа Крейга? Иначе говоря, если заданы два операционных числа М и N, а также два произвольных

Стр. 146

числа А и В, то обязательно ли существуют такие числа X и У, при которых X порождает M(AY), а У порождает N(BX)

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

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

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

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

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

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

б) X порождает М(АУ) а У порождает ВХ;

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

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

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

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

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

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

— Именно так,— подтвердил Фергюссон.— Более того, если заданы три произвольных операционных

Стр.147

числа М, N и Р, то должны существовать такие числа X, У и Z, при которых X порождает M(Y), Y порождает N(Z), a Z порождает Р(Х).

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

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

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

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

Решени

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

* Что соответствует случаю, когда одно или два числа из тройки А, В, С мы полагаем равными единице.

Стр. 148

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

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

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

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

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

5. Единственное, что нам нужно — это найти такое число X, которое порождало бы число А2ВХ. Тогда,

Стр. 149

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

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

7. Здесь нам необходимо найти такое число X, которое порождало бы число М(AN2BX); согласно второму принципу Крейга, таким числом X является число

Стр. 150

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

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

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

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

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

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

Y=N2P2M32N2P2M3,

Z=P2M32N2P2M3.

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

Читатель сам может легко убедиться, что действи-

Стр.151

тельно X порождает обращение У, 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), число У порождает B(Z), а число Z порождает С(Х). Таким образом, мы нашли еще один способ решения данной задачи.