Пусть М—некоторое число, состоящее из цифр 3, 4 или 5, и пусть F — произвольная операция. Я буду говорить, что число М определяет операцию F, имея в виду, что для любых двух чисел X и Y, в случае если X порождает Y, число М(Х) порождает число F(Y). Например, если число X порождает число Y, то число 4Х порождает обращение числа Y (согласно правилу 3), и поэтому я буду говорить, что число 4 определяет или обозначает операцию обращения данного числа. Аналогичным образом в соответствии с правилом 4 число 5 определяет операцию повторения, а число 3 — операцию ассоциации, то есть операцию получения ассоциата данного числа. Далее, предположим, что F представляет собой операцию, которая, если ее выполнить над числом X, дает нам ассоциат повторения X. Другими словами, F(X) есть ассоциат повторения числа X. Существует ли число М, которое описывает эту операцию, и если да, то что это за число?
— Очевидно, 35,— ответил Мак-Каллох, — потому что если число X порождает число Y, то число 5Х порождает повторение числа У; значит, число 35X порождает ассоциат повторения У. Таким образом, число 35 обозначает операцию получения ассоциата повторения некоторого заданного числа X.
— Совершенно верно, — подтвердил Крейг. — А теперь, когда мы определили, каким образом число М представляет собой ту или иную операцию, мы будем называть эту операцию операцией М. Так, например, операция 4 будет операцией обращения, операция 5 представляет собой операцию повторения, операция 35 является операцией получения ассоциата повторения и так далее.
Вместе с тем возникает вопрос, — продолжал он, — возможно ли, чтобы два различных числа описывали одну и ту же операцию? Иначе, могут ли существовать операционные числа М и N, такие, что при М, не равном N, операция М оказывается тождественной операции N?
Мак-Каллох на мгновение задумался.
— Ну, конечно, — сказал он. — Ведь, например, числа 45 и 54 различны, однако они определяют собой одну и ту же операцию, поскольку обращение повторения некоторого числа есть то же самое, что и повторение его обращения.
— Правильно, — согласился Крейг, — хотя, по правде говоря, я имел в виду совсем другой пример. Прежде всего, какую операцию описывает число 44?
— Ну, это ясно, — ответил Мак-Каллох, — Операция 44, если ею подействовать на заданное число X, дает нам обращение обращения этого числа, то есть само X. Правда, я не знаю, как назвать такую операцию, которая при воздействии на число X дает нам само это число.
— В математике такая операция называется обычно операцией тождества, — продолжал свои объяснения Крейг, — и поэтому число 44 будет определять собой именно операцию тождества. Но ту же самую операцию будет определять и число 4444 или, например, любое другое число, составленное из четного количества четверок. Таким образом, существует бесконечно много чисел, описывающих подобную операцию. А вообще говоря, если задано некоторое операционное число М и если оно следует за четным количеством четверок или предшествует ему (или же имеет место и то и другое одновременно), то это число М описывает ту же самую операцию, что и само отдельно взятое М.
— Понятно, — кивнул Мак-Каллох.
— А теперь, — пояснил далее Крейг, — если нам заданно операционное число М и произвольное число X, то, чтобы обозначить результат воздействия операции М на число X, я буду просто писать М(Х). Например, число 3(Х) будет представлять собой ассоциат X, 4(Х) будет обращением числа X, 5(Х) окажется повторением числа X, а число 435(X) будет представлять собой вращение ассоциата повторения числа X. Понятны тебе эти обозначения?
— Вполне, — ответил Мак-Каллох.
— Надеюсь, теперь ты не будешь путать запись М(Х) с записью MX. Ведь первая из них обозначает результат воздействия операции М на число X, в то время как вторая утверждает лишь то, что за числом М следует число X, — а это совсем разные вещи! Например, запись 3(5) обозначает вовсе не 35, а 525.
— Это мне тоже понятно, — сказал Мак-Каллох. — Однако не может ли случиться так — хотя бы в силу чистой случайности, — чтобы число М(Х) совпадало с MX?
— Интересный вопрос, — ответил Крейг. — Мне нужно его обдумать!
— Может, сначала выпьем еще по чашечке чаю? — предложил Мак-Каллох.
— С удовольствием! — согласился Крейг.
Пока наши друзья наслаждаются чаем, мне хотелось бы предложить вам несколько занимательных задач с операционными числами. Они позволят читателям приобрести необходимый опыт в использовании обозначений типа М(Х), которые будут играть важную роль при дальнейшем изложении.
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.
Принцип Крейга
— Ты так и не рассказал мне, в чем же состоит твой принцип, — сказал Мак-Каллох, когда друзья покончили с чаем. — Полагаю, что об операционных числах и операциях мы заговорили именно в связи с этим принципом?
— Ну, конечно, — отвечал Крейг. — Теперь, я думаю, ты легко сможешь понять идею этого принципа. Помнишь задачи, которые ты предлагал мне раньше? Ну, например, найти число 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). Например если У порождает 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 (Х)
— Я приготовил для тебя еще несколько задачек, — сказал Мак-Каллох, — однако сегодня уже поздно. Оставайся-ка ночевать у меня. А завтра мы с тобой поговорим подробнее.
У Крейга как раз было несколько свободных дней, и поэтому он с удовольствием принял приглашение Мак-Каллоха.
Некоторые варианты принципа Крейга
Наутро после плотного завтрака — а хозяин оказался человеком очень гостеприимным — Мак-Каллох предложил Крейгу следующие задачи.
21. Найти число X, которое порождает число 7Х7Х.
22. Найти число X, которое порождает обращение числа 9Х.
23. Найти число X, которое порождает ассоциат числа 89х.
— Очень мило! — воскликнул Крейг, после того как покончил с решением последней задачи. — Ни одну из их задач нельзя решить с помощью того принципа, о котором я тебе рассказывал вчера.
— Вот именно! — рассмеялся Мак-Каллох.
— И все-таки, — возразил Крейг, — решение всех грех задач подчиняется некой общей идее: во-первых, конкретные числа 7, 5 и 89 не играют никакой роли; для любого данного числа А существует определенное число X, которое порождает повторение числа АХ, еще какое-то X порождает обращение АХ; наконец, есть X, порождающее ассоциат числа АХ. Кроме того, существует также некое число X, которое порождает повторение обращения числа АХ или, например, обращение ассоциата АХ. Фактически это означает, что для любого операционного числа М и для любого заданного числа А должно существовать некоторое число X, которое порождает М(АХ), то есть число, полученное в результате применения операции М к числу АХ.
24. Крейг, разумеется, был прав: для любого операционного числа М и для любого заданного числа А должно найтись некоторое число X, которое порождает число М(АХ). Будем называть это правило вторым принципом Крейга. Как же доказать этот принцип? И как при заданном операционном числе М и заданном А найти в явном виде такое число X, которое порождает М(АХ)?
25. — Мне только что пришел в голову еще один вопрос, — сказал Мак-Каллох. — Пусть для любого числа X величина X обозначает обращение этого X. Можешь ли ты найти такое число X, которое порождает Х67? (Иначе, существует ли такое число X, которое порождает обращение числа X, за которым следует число 67?) В общем виде этот вопрос можно сформулировать так: действительно ли для любого числа А существует некоторое число X, которое порождает ХА?
26. — Мне в голову пришел еще один вопрос, — сказал Мак-Каллох. — Существует ли такое число X, которое порождает повторение числа Х67? Или, в более общем виде: действительно ли для любого числа А существует такое число X, которое порождает повторение числа ХА? Или, если задать вопрос в еще более общем виде: действительно ли для любого числа А и для любого операционного числа М должно существовать некоторое число X, которое порождает м(ХА)?
Обсуждение
Принцип Крейга справедлив не только для второй машины Мак-Каллоха, но и для первой — а в сущности и для любой машины, в которую заложены правила 1 и 2. Это означает, что, как бы мы ни расширяли первую машину Мак-Каллоха, вводя в нее новые правила, работа результирующего устройства все равно будет подчиняться принципу Крейга (а фактически обоим его принципам).
Первый принцип Крейга связан с одним из знаменитых результатов теории вычислимых функций, известным под названием теоремы о рекурсии (или, как ее иногда называют, теоремы о неподвижной точке). С помощью правил 1 и 2, предложенных Мак-Каллохом, этот результат получается, пожалуй, наиболее простым способом. Кроме того, эти правила обладают еще одним занятным свойством (связанным уже с другим знаменитым результатом теории вычислимых функций, известным под названием теоремы о двойной рекурсии), о котором пойдет речь в следующей главе. Наконец, все эти сведения имеют отношение к теории самовоспроизводящихся машин и теории клонирования.
Решения
1. — С помощью твоей теперешней машины можно получить бесконечное множество чисел, которые порождают сами себя, — сказал Крейг.
— Это верно, — согласился Мак-Каллох. — Но как ты это докажешь?
— Начнем с того, — сказал Крейг, — что будем называть некое число SA числом, если оно обладает тем свойством, что для любых чисел X и У в случае, если X порождает V, число SX порождает ассоциат У. До того как ты ввел свое новое правило, единственным А-числом у нас было число 3. Однако для твоей нынешней машины существует бесконечное множество А-чисел, причем для любого А-числа S число S2S обязательно должно порождать само себя, поскольку число S2S порождает ассоциат числа S, который и есть S2S.
А как ты догадался, что существует бесконечное множество А-чисел? — спросил Мак-Каллох.
Ну, во-первых, — ответил Крейг, — надеюсь, ты не будешь возражать, что при любых числах X и У, если число X порождает У, то число 44Х будет также порождать У?
— Удачное наблюдение! — воскликнул Мак-Каллох. — Конечно, ты прав: ведь если X порождает У, то число 4Х порождает обращение числа У, а значит, число 44 X должно порождать обращение обращения У — то есть само это число У.
— Прекрасно, — продолжал Крейг. — Таким образом, если X порождает У, то число 44Х будет тоже порождать У, и поэтому число 344Х будет порождать ассоциат числа У. Значит, 344 тоже представляет собой А-число. А раз 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
— Очевидно, 35,— ответил Мак-Каллох, — потому что если число X порождает число Y, то число 5Х порождает повторение числа У; значит, число 35X порождает ассоциат повторения У. Таким образом, число 35 обозначает операцию получения ассоциата повторения некоторого заданного числа X.
— Совершенно верно, — подтвердил Крейг. — А теперь, когда мы определили, каким образом число М представляет собой ту или иную операцию, мы будем называть эту операцию операцией М. Так, например, операция 4 будет операцией обращения, операция 5 представляет собой операцию повторения, операция 35 является операцией получения ассоциата повторения и так далее.
Вместе с тем возникает вопрос, — продолжал он, — возможно ли, чтобы два различных числа описывали одну и ту же операцию? Иначе, могут ли существовать операционные числа М и N, такие, что при М, не равном N, операция М оказывается тождественной операции N?
Мак-Каллох на мгновение задумался.
— Ну, конечно, — сказал он. — Ведь, например, числа 45 и 54 различны, однако они определяют собой одну и ту же операцию, поскольку обращение повторения некоторого числа есть то же самое, что и повторение его обращения.
— Правильно, — согласился Крейг, — хотя, по правде говоря, я имел в виду совсем другой пример. Прежде всего, какую операцию описывает число 44?
— Ну, это ясно, — ответил Мак-Каллох, — Операция 44, если ею подействовать на заданное число X, дает нам обращение обращения этого числа, то есть само X. Правда, я не знаю, как назвать такую операцию, которая при воздействии на число X дает нам само это число.
— В математике такая операция называется обычно операцией тождества, — продолжал свои объяснения Крейг, — и поэтому число 44 будет определять собой именно операцию тождества. Но ту же самую операцию будет определять и число 4444 или, например, любое другое число, составленное из четного количества четверок. Таким образом, существует бесконечно много чисел, описывающих подобную операцию. А вообще говоря, если задано некоторое операционное число М и если оно следует за четным количеством четверок или предшествует ему (или же имеет место и то и другое одновременно), то это число М описывает ту же самую операцию, что и само отдельно взятое М.
— Понятно, — кивнул Мак-Каллох.
— А теперь, — пояснил далее Крейг, — если нам заданно операционное число М и произвольное число X, то, чтобы обозначить результат воздействия операции М на число X, я буду просто писать М(Х). Например, число 3(Х) будет представлять собой ассоциат X, 4(Х) будет обращением числа X, 5(Х) окажется повторением числа X, а число 435(X) будет представлять собой вращение ассоциата повторения числа X. Понятны тебе эти обозначения?
— Вполне, — ответил Мак-Каллох.
— Надеюсь, теперь ты не будешь путать запись М(Х) с записью MX. Ведь первая из них обозначает результат воздействия операции М на число X, в то время как вторая утверждает лишь то, что за числом М следует число X, — а это совсем разные вещи! Например, запись 3(5) обозначает вовсе не 35, а 525.
— Это мне тоже понятно, — сказал Мак-Каллох. — Однако не может ли случиться так — хотя бы в силу чистой случайности, — чтобы число М(Х) совпадало с MX?
— Интересный вопрос, — ответил Крейг. — Мне нужно его обдумать!
— Может, сначала выпьем еще по чашечке чаю? — предложил Мак-Каллох.
— С удовольствием! — согласился Крейг.
Пока наши друзья наслаждаются чаем, мне хотелось бы предложить вам несколько занимательных задач с операционными числами. Они позволят читателям приобрести необходимый опыт в использовании обозначений типа М(Х), которые будут играть важную роль при дальнейшем изложении.
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.
Принцип Крейга
— Ты так и не рассказал мне, в чем же состоит твой принцип, — сказал Мак-Каллох, когда друзья покончили с чаем. — Полагаю, что об операционных числах и операциях мы заговорили именно в связи с этим принципом?
— Ну, конечно, — отвечал Крейг. — Теперь, я думаю, ты легко сможешь понять идею этого принципа. Помнишь задачи, которые ты предлагал мне раньше? Ну, например, найти число 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). Например если У порождает 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 (Х)
— Я приготовил для тебя еще несколько задачек, — сказал Мак-Каллох, — однако сегодня уже поздно. Оставайся-ка ночевать у меня. А завтра мы с тобой поговорим подробнее.
У Крейга как раз было несколько свободных дней, и поэтому он с удовольствием принял приглашение Мак-Каллоха.
Некоторые варианты принципа Крейга
Наутро после плотного завтрака — а хозяин оказался человеком очень гостеприимным — Мак-Каллох предложил Крейгу следующие задачи.
21. Найти число X, которое порождает число 7Х7Х.
22. Найти число X, которое порождает обращение числа 9Х.
23. Найти число X, которое порождает ассоциат числа 89х.
— Очень мило! — воскликнул Крейг, после того как покончил с решением последней задачи. — Ни одну из их задач нельзя решить с помощью того принципа, о котором я тебе рассказывал вчера.
— Вот именно! — рассмеялся Мак-Каллох.
— И все-таки, — возразил Крейг, — решение всех грех задач подчиняется некой общей идее: во-первых, конкретные числа 7, 5 и 89 не играют никакой роли; для любого данного числа А существует определенное число X, которое порождает повторение числа АХ, еще какое-то X порождает обращение АХ; наконец, есть X, порождающее ассоциат числа АХ. Кроме того, существует также некое число X, которое порождает повторение обращения числа АХ или, например, обращение ассоциата АХ. Фактически это означает, что для любого операционного числа М и для любого заданного числа А должно существовать некоторое число X, которое порождает М(АХ), то есть число, полученное в результате применения операции М к числу АХ.
24. Крейг, разумеется, был прав: для любого операционного числа М и для любого заданного числа А должно найтись некоторое число X, которое порождает число М(АХ). Будем называть это правило вторым принципом Крейга. Как же доказать этот принцип? И как при заданном операционном числе М и заданном А найти в явном виде такое число X, которое порождает М(АХ)?
25. — Мне только что пришел в голову еще один вопрос, — сказал Мак-Каллох. — Пусть для любого числа X величина X обозначает обращение этого X. Можешь ли ты найти такое число X, которое порождает Х67? (Иначе, существует ли такое число X, которое порождает обращение числа X, за которым следует число 67?) В общем виде этот вопрос можно сформулировать так: действительно ли для любого числа А существует некоторое число X, которое порождает ХА?
26. — Мне в голову пришел еще один вопрос, — сказал Мак-Каллох. — Существует ли такое число X, которое порождает повторение числа Х67? Или, в более общем виде: действительно ли для любого числа А существует такое число X, которое порождает повторение числа ХА? Или, если задать вопрос в еще более общем виде: действительно ли для любого числа А и для любого операционного числа М должно существовать некоторое число X, которое порождает м(ХА)?
Обсуждение
Принцип Крейга справедлив не только для второй машины Мак-Каллоха, но и для первой — а в сущности и для любой машины, в которую заложены правила 1 и 2. Это означает, что, как бы мы ни расширяли первую машину Мак-Каллоха, вводя в нее новые правила, работа результирующего устройства все равно будет подчиняться принципу Крейга (а фактически обоим его принципам).
Первый принцип Крейга связан с одним из знаменитых результатов теории вычислимых функций, известным под названием теоремы о рекурсии (или, как ее иногда называют, теоремы о неподвижной точке). С помощью правил 1 и 2, предложенных Мак-Каллохом, этот результат получается, пожалуй, наиболее простым способом. Кроме того, эти правила обладают еще одним занятным свойством (связанным уже с другим знаменитым результатом теории вычислимых функций, известным под названием теоремы о двойной рекурсии), о котором пойдет речь в следующей главе. Наконец, все эти сведения имеют отношение к теории самовоспроизводящихся машин и теории клонирования.
Решения
1. — С помощью твоей теперешней машины можно получить бесконечное множество чисел, которые порождают сами себя, — сказал Крейг.
— Это верно, — согласился Мак-Каллох. — Но как ты это докажешь?
— Начнем с того, — сказал Крейг, — что будем называть некое число SA числом, если оно обладает тем свойством, что для любых чисел X и У в случае, если X порождает V, число SX порождает ассоциат У. До того как ты ввел свое новое правило, единственным А-числом у нас было число 3. Однако для твоей нынешней машины существует бесконечное множество А-чисел, причем для любого А-числа S число S2S обязательно должно порождать само себя, поскольку число S2S порождает ассоциат числа S, который и есть S2S.
А как ты догадался, что существует бесконечное множество А-чисел? — спросил Мак-Каллох.
Ну, во-первых, — ответил Крейг, — надеюсь, ты не будешь возражать, что при любых числах X и У, если число X порождает У, то число 44Х будет также порождать У?
— Удачное наблюдение! — воскликнул Мак-Каллох. — Конечно, ты прав: ведь если X порождает У, то число 4Х порождает обращение числа У, а значит, число 44 X должно порождать обращение обращения У — то есть само это число У.
— Прекрасно, — продолжал Крейг. — Таким образом, если X порождает У, то число 44Х будет тоже порождать У, и поэтому число 344Х будет порождать ассоциат числа У. Значит, 344 тоже представляет собой А-число. А раз 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23