7. Здесь нам необходимо найти такое число X, которое порождало бы число М(AN2BX); согласно второму принципу Крейга, таким числом X является число 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.
Читатель сам может легко убедиться, что действительно 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 порождает С(Х). Таким образом, мы нашли еще один способ решения данной задачи.
Остановимся, попробуем обобщить!
Решения
Ключ
Решения
Часть четвертая. Разрешима или неразрешима наша задача?
Логическая машина Фергюссона
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.
Читатель сам может легко убедиться, что действительно 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 порождает С(Х). Таким образом, мы нашли еще один способ решения данной задачи.
Остановимся, попробуем обобщить!
Два дня спустя полицейское начальство из Скотланд-Ярда внезапно и совершенно неожиданно для Крейга срочно откомандировало его в Норвегию для расследования, хотя и интересного, но нас не касающегося. Поэтому я воспользуюсь отсутствием Крейга, чтобы поделиться с вами кое-какими собственными соображениями по поводу числовых машин Мак-Каллоха. Те же читатели, которым не терпится узнать решение загадки сейфа из Монте-Карло, могут отложить чтение этой главы на потом.
Математики обожают обобщать! Сплошь и рядом случается так: некий математик по имени X доказывает новую теорему и публикует доказательство в научном журнале. Потом проходит полгода и появляется другой математик, Y, который вдруг заявляет: «Ну ладно, неплохую теоремку доказал этот X, однако я могу доказать гораздо более общий случай!» И тут же печатает статью под названием «Об одном обобщении георемы Х-а». Или же Y оказывается похитрее и поступает следующим образом: сначала он втайне обобщает теорему, доказанную Х-м, а потом исследует какой-нибудь частный случай своего обобщения. Этот частный случай по внешнему виду обычно настолько отличается от исходной теоремы, предложенной Х-м, что Y вполне может опубликовать полученный результат в качестве новой, оригинальной теоремы. Тут на сцене, естественно, появляется третий математик по имени Z: этого Z никак не оставляет чувство, что где-то теоремы Х-а и Y-a в чем-то важном очень сходны. Он начинает напряженно работать и… обнаруживает некий общий принцип. Z тут же публикует работу, в которой формулирует и доказывает этот новый общий принцип, а в заключение добавляет: «Теоремы, предложенные Х-м и 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, должна подчиняться также и всем законам Фергюссона.
Не сообразит ли читатель, как доказать все эти теоремы?
Математики обожают обобщать! Сплошь и рядом случается так: некий математик по имени X доказывает новую теорему и публикует доказательство в научном журнале. Потом проходит полгода и появляется другой математик, Y, который вдруг заявляет: «Ну ладно, неплохую теоремку доказал этот X, однако я могу доказать гораздо более общий случай!» И тут же печатает статью под названием «Об одном обобщении георемы Х-а». Или же Y оказывается похитрее и поступает следующим образом: сначала он втайне обобщает теорему, доказанную Х-м, а потом исследует какой-нибудь частный случай своего обобщения. Этот частный случай по внешнему виду обычно настолько отличается от исходной теоремы, предложенной Х-м, что Y вполне может опубликовать полученный результат в качестве новой, оригинальной теоремы. Тут на сцене, естественно, появляется третий математик по имени Z: этого Z никак не оставляет чувство, что где-то теоремы Х-а и Y-a в чем-то важном очень сходны. Он начинает напряженно работать и… обнаруживает некий общий принцип. Z тут же публикует работу, в которой формулирует и доказывает этот новый общий принцип, а в заключение добавляет: «Теоремы, предложенные Х-м и 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, которое есть число А52А52, то есть число АХ). Тем самым мы доказали теорему 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. Для заданного операционного числа М числом А, порождающим М(Х), оказывается число М52М52. (Сравните его с прежним решением — числом М32МЗ, полученным для машины, в которой вместо правила 4 используется правило 2.) Если теперь задано операционное число М и некое число А, то числом X, порождающим M(AX), будет число М52АМ52. (Сравните его с прежним решением — М32АМЗ.) Построенные решения показывают нам, что оба принципа Крейга могут быть получены на основании правил 1 и 4. Впрочем, я сформулировал гораздо более общее утверждение, а именно: для того чтобы получить принципы Крейга, достаточно одного только закона Мак-Каллоха (теорема 2). Это утверждение можно доказать тем же способом, который использовался нами в гл. 10. В самом деле, для любого заданного операционного числа М существует некое число Y, которое порождает MY; отсюда ясно, что число М У порождает М(М У). Поэтому число X порождает М(Х), где Х = МУ. Точно так же для любого числа А, если имеется некоторое число У, порождающее AMY, число МУ порождает М(АМУ) и, следовательно, число X порождает М(АХ) при Х = МУ.
Что же касается теоремы 3, то ее можно доказать так же, как это делалось в предыдущей главе. [Например, если даны операционные числа М и N и если выполняется второй принцип Крейга, то существует некое число X, которое порождает M(N2X). Если теперь мы обозначим число N2X через У, то получим, что число X порождает М(У), а число У порождаетN(X)]
А теперь рассмотрим машину, которая подчиняется выведенным Мак-Каллохом правилам 1, 3 и 4. Числом, порождающим обращение самого себя, является, например, число 452452 (оно порождает обращение повторения числа 452, или, другими словами, обращение числа 452452). (Сравните его с предыдущим решением 43243.) Числом, которое порождает повторение обращения самого себя, является число 54525452. (Сравните его с прежним решением 5432543.)
Далее, рассмотрим машину, которая подчиняется правилам 1, 2 и 4. Мы знаем, что число 33233 порождает свой собственный ассоциат точно так же, как и число 352352. Что касается числа X, порождающего повторение самого себя, то у нас уже имеются два решения — это числа 35235 и 552552. Что же касается числа X, порождающего ассоциат повторения самого себя, то одним решением служит число 3532353; другим — число 35523552. Наконец, для числа, которое порождает повторение своего собственного ассоциата, также существуют два решения — это число 5332533 или число 53525352.
Наконец, рассмотрим некоторую произвольную машину, которая подчиняется по меньшей мере двум из правил Мак-Каллоха, а именно: правилам 1 и 4. Для заданного операционного числа М числом А, порождающим М(Х), оказывается число М52М52. (Сравните его с прежним решением — числом М32МЗ, полученным для машины, в которой вместо правила 4 используется правило 2.) Если теперь задано операционное число М и некое число А, то числом X, порождающим M(AX), будет число М52АМ52. (Сравните его с прежним решением — М32АМЗ.) Построенные решения показывают нам, что оба принципа Крейга могут быть получены на основании правил 1 и 4. Впрочем, я сформулировал гораздо более общее утверждение, а именно: для того чтобы получить принципы Крейга, достаточно одного только закона Мак-Каллоха (теорема 2). Это утверждение можно доказать тем же способом, который использовался нами в гл. 10. В самом деле, для любого заданного операционного числа М существует некое число Y, которое порождает MY; отсюда ясно, что число М У порождает М(М У). Поэтому число X порождает М(Х), где Х = МУ. Точно так же для любого числа А, если имеется некоторое число У, порождающее AMY, число МУ порождает М(АМУ) и, следовательно, число X порождает М(АХ) при Х = МУ.
Что же касается теоремы 3, то ее можно доказать так же, как это делалось в предыдущей главе. [Например, если даны операционные числа М и N и если выполняется второй принцип Крейга, то существует некое число X, которое порождает M(N2X). Если теперь мы обозначим число N2X через У, то получим, что число X порождает М(У), а число У порождаетN(X)]
Ключ
Дело, по которому Крейг поехал в Норвегию, заняло у него гораздо меньше времени, чем он предполагал, и ровно через три недели инспектор возвратился домой. Дома его ждала записка от Мак-Каллоха:
Крейг приехал к Мак-Каллоху минут через пятнадцать после того, как там появился Фергюссон.
— С благополучным возвращением! — приветствовал приятеля Мак-Каллох.
— Пока вас не было, — сразу же сообщил Фергюссон, — Мак-Каллох изобрел новую числовую машину!
— Ну да? — удивился Крейг.
— Я занимался этим не один, — сказал Мак-Каллох, — Фергюссон тоже приложил к ней руку. А вообще-то машина интересная; на этот раз в нее введены следующие четыре правила:
правило MI: для любого числа X число 2X2 порождает X;
правил о МII: если число X порождает число У, то число 6Х порождает число 2 У;
правило MIII: если число X порождает число У, то число 4Х порождает число У (как и в случае предыдущей машины);
правило MIV: если число X порождает число У, то число 5Х порождает число УУ (как и в случае предыдущей машины).
— Эта машина, — продолжал Мак-Каллох, — обладает всеми прекрасными свойствами моей последней машины — она подчиняется двум твоим принципам и, кроме того, закону двойных аналогов Фергюссона.
Крейг довольно долго и внимательно изучал эти правила. Наконец он сказал:
— Что-то мне никак не удается сдвинуться с места. Не могу даже найти число, которое порождает само себя. Есть тут такие числа?
— Есть, — ответил Мак-Каллох, — но с помощью этой машины найти их гораздо труднее, чем в предыдущем случае. Честно говоря, я тоже не смог решить эту задачу. А вот Фергюссон с ней справился. Более того, теперь мы знаем, что такое короткое число, порождающее само себя, состоит из десяти цифр.
Крейг опять глубоко задумался.
— А что, первых двух правил недостаточно для нахождения такого числа? — поинтересовался он наконец.
— Нет, конечно! — ответил Мак-Каллох. — Для получения этого числа нам необходимы все четыре правила.
— Удивительное дело, — пробормотал Крейг и вновь погрузился в глубокое раздумье.
— О господи! — вдруг воскликнул он, буквально подскочив на стуле. — Да ведь это же решение загадки сейфа!
— О чем это вы? — спросил Фергюссон.
— А-а, прошу прощения! Вы ведь не знаете, — сказал Крейг и поведал им всю историю с банковским сейфом из Монте-Карло.
— Надеюсь, вы понимаете, что наш разговор сугубо конфиденциальный, — заключил свой рассказ Крейг. — А теперь, Мак-Каллох, если ты дашь мне число, которое порождает само себя, то я сразу же смогу назвать комбинацию, которая откроет замок сейфа.
Итак, читателю предлагаются три задачи.
1) Какое число X порождает само себя в последней машине?
2) Какая комбинация открывает замок сейфа?
3) Как связаны между собой первые два вопроса?
Как и обещал Мартинес, совет директоров банка прислал Крейгу солидное денежное вознаграждение. Крейг настоял на том, чтобы разделить эти деньги с Мак-Каллохом и Фергюссоном. Свой успех трое друзей решили отпраздновать, заказав шикарный ужин в ресторане «У льва».
— А знаете, — сказал Крейг, отведав превосходного хереса. — Пожалуй, это было одно из самых интересных дел в моей практике. Подумать только, числовые машины, созданные из чисто интеллектуального любопытства, и вдруг оказывают такую неоценимую помощь на практике!
Дорогой Крейг!— Вот и отлично! — сказал себе Крейг. — Я вернулся как раз вовремя!
Если ты случайно вернешься из Норвегии до 12 мая (это пятница), то приходи ко мне в этот день обедать. Фергюссона я уже пригласил.
С приветом
Норман Мак-Каллох
Крейг приехал к Мак-Каллоху минут через пятнадцать после того, как там появился Фергюссон.
— С благополучным возвращением! — приветствовал приятеля Мак-Каллох.
— Пока вас не было, — сразу же сообщил Фергюссон, — Мак-Каллох изобрел новую числовую машину!
— Ну да? — удивился Крейг.
— Я занимался этим не один, — сказал Мак-Каллох, — Фергюссон тоже приложил к ней руку. А вообще-то машина интересная; на этот раз в нее введены следующие четыре правила:
правило MI: для любого числа X число 2X2 порождает X;
правил о МII: если число X порождает число У, то число 6Х порождает число 2 У;
правило MIII: если число X порождает число У, то число 4Х порождает число У (как и в случае предыдущей машины);
правило MIV: если число X порождает число У, то число 5Х порождает число УУ (как и в случае предыдущей машины).
— Эта машина, — продолжал Мак-Каллох, — обладает всеми прекрасными свойствами моей последней машины — она подчиняется двум твоим принципам и, кроме того, закону двойных аналогов Фергюссона.
Крейг довольно долго и внимательно изучал эти правила. Наконец он сказал:
— Что-то мне никак не удается сдвинуться с места. Не могу даже найти число, которое порождает само себя. Есть тут такие числа?
— Есть, — ответил Мак-Каллох, — но с помощью этой машины найти их гораздо труднее, чем в предыдущем случае. Честно говоря, я тоже не смог решить эту задачу. А вот Фергюссон с ней справился. Более того, теперь мы знаем, что такое короткое число, порождающее само себя, состоит из десяти цифр.
Крейг опять глубоко задумался.
— А что, первых двух правил недостаточно для нахождения такого числа? — поинтересовался он наконец.
— Нет, конечно! — ответил Мак-Каллох. — Для получения этого числа нам необходимы все четыре правила.
— Удивительное дело, — пробормотал Крейг и вновь погрузился в глубокое раздумье.
— О господи! — вдруг воскликнул он, буквально подскочив на стуле. — Да ведь это же решение загадки сейфа!
— О чем это вы? — спросил Фергюссон.
— А-а, прошу прощения! Вы ведь не знаете, — сказал Крейг и поведал им всю историю с банковским сейфом из Монте-Карло.
— Надеюсь, вы понимаете, что наш разговор сугубо конфиденциальный, — заключил свой рассказ Крейг. — А теперь, Мак-Каллох, если ты дашь мне число, которое порождает само себя, то я сразу же смогу назвать комбинацию, которая откроет замок сейфа.
Итак, читателю предлагаются три задачи.
1) Какое число X порождает само себя в последней машине?
2) Какая комбинация открывает замок сейфа?
3) Как связаны между собой первые два вопроса?
Эпилог
Рано утром следующего дня Крейг, подыскав надежного человека, отправил в Монте-Карло пакет, адресованный Мартинесу, в котором была записана найденная им накануне кодовая комбинация. Курьер прибыл вовремя, и сейф был благополучно открыт.Как и обещал Мартинес, совет директоров банка прислал Крейгу солидное денежное вознаграждение. Крейг настоял на том, чтобы разделить эти деньги с Мак-Каллохом и Фергюссоном. Свой успех трое друзей решили отпраздновать, заказав шикарный ужин в ресторане «У льва».
— А знаете, — сказал Крейг, отведав превосходного хереса. — Пожалуй, это было одно из самых интересных дел в моей практике. Подумать только, числовые машины, созданные из чисто интеллектуального любопытства, и вдруг оказывают такую неоценимую помощь на практике!
Решения
Сначала еще несколько слов о загадке сейфа из Монте-Карло. В последнем условии Фаркуса не говорится, что требуемая комбинация у непременно должна отличаться от комбинации х. Поэтому если предположить, что х и у представляют собой одну и ту же комбинацию, то указанное условие можно будет прочитать так: «Пусть комбинация х родственна по отношению к комбинации х, тогда если комбинация х блокирует замок, то комбинация х будет нейтральной; если же комбинация х оказывается нейтральной, то комбинация х блокирует замок». Однако невозможно, чтобы комбинация х одновременно была нейтральной и блокировала замок. Следовательно, если комбинация х родственна но отношению к х, тогда эта комбинация не может ни оказаться нейтральной, ни блокировать замок. А значит, она должна этот замок открывать! Таким образом, если мы сумеем найти комбинацию х, которая родственна самой себе, то такая комбинация х обязательно откроет нам замок.
Конечно, Крейг понял это еще задолго до того, как вернулся в Лондон. Но как найти комбинацию х, которая родственна самой себе? Именно на этот вопрос Крейг и не мог ответить до тех пор, пока судьба не столкнула его с третьей машиной Мак-Каллоха.
Оказывается, задача нахождения комбинации, которая, согласно условию Фаркуса, является родственной самой себе, по своей сути тождественна задаче нахождения числа, которое порождает само себя в последней машине Мак-Каллоха. Единственное существенное отличие заключается в том, что кодовые комбинации для замка — это цепочки букв, тогда как числовые машины работают с цепочками цифр. Однако первую задачу можно легко преобразовать ко второй, и наоборот, следующим простым приемом.
Во-первых, мы рассматриваем лишь комбинации из букв Q, L, V, J? (совершенно очевидно, что только эти буквы играют в задаче существенную роль). Предположим теперь, что вместо этих букв мы будем использовать собственно цифры 2, 6, 4, 5 (то есть 2 вместо Q, 6 вместо L, 4 вместо V и 5 вместо R). Для удобства запишем это так:
(1). Для любого числа Х число 2X2 является родственным числу X.
(2). Если число X родственно числу Y, то число 6Х оказывается родственным числу 2 У.
(3). Если число X родственно числу У, то число 4Х родственно числу Т.
(4). Если число X родственно числу У, то число 5Х родственно числу УУ.
Сразу видно, что это — точно те же правила, которым подчиняется последняя машина Мак-Каллоха, с той лишь разницей, что вместо слова «порождает» используется слово «родственно». (Конечно, я мог бы воспользоваться словом «порождает» и в гл. 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 и У, если число X порождает число У, число НХ порождало бы число Y2Y2. Если мы сумеем найти это число Н, тогда при любом У число Н2 У2 будет порождать число У2 У2 (потому что, согласно правилу MI, число 2У2 порождает число У), а значит, число Н2Н2 будет порождать число Н2Н2; тем самым мы получим искомое число N. Но как найти число Н?
Эта задача сводится к следующей: как, исходя из заданного числа У и последовательно применяя операции, которые способна выполнять наша машина, получить число У2У2? Так вот, построить число У2У2 из числа У можно следующим способом: сначала построить обращение числа У, получив число У; затем слева от «у» приписать цифру 2, получив тем самым число 2У; далее построить обращение числа 2Т, получив число У2; наконец, построить повторение числа У2, получив число У2 У2. Эти операции обозначаются соответственно операционными числами 4, 6, 4 и 5, поэтому в качестве Н мы выберем число 5464.
Давайте проверим, подходит ли нам найденное число Н. Пусть число X порождает число У; тогда мы должны выяснить, действительно ли число 5464Н порождает число У2У2. Но поскольку X порождает У, то число 4Х порождает число У (в соответствии с правилом MIII); значит, число 64Х порождает число 2V (в соответствии с правилом МII). Отсюда следует, что число 464Х порождает число У2 (в соответствии с правилом MIII), и, стало быть, число 5464Х порождает число У2У2 (в соответствии с правилом MIV). Итак, мы получили, что если X порождает У, то число НХ в самом деле порождает число 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 действительно является родственной самой себе.
Конечно, Крейг понял это еще задолго до того, как вернулся в Лондон. Но как найти комбинацию х, которая родственна самой себе? Именно на этот вопрос Крейг и не мог ответить до тех пор, пока судьба не столкнула его с третьей машиной Мак-Каллоха.
Оказывается, задача нахождения комбинации, которая, согласно условию Фаркуса, является родственной самой себе, по своей сути тождественна задаче нахождения числа, которое порождает само себя в последней машине Мак-Каллоха. Единственное существенное отличие заключается в том, что кодовые комбинации для замка — это цепочки букв, тогда как числовые машины работают с цепочками цифр. Однако первую задачу можно легко преобразовать ко второй, и наоборот, следующим простым приемом.
Во-первых, мы рассматриваем лишь комбинации из букв Q, L, V, J? (совершенно очевидно, что только эти буквы играют в задаче существенную роль). Предположим теперь, что вместо этих букв мы будем использовать собственно цифры 2, 6, 4, 5 (то есть 2 вместо Q, 6 вместо L, 4 вместо V и 5 вместо R). Для удобства запишем это так:
Q L V RТеперь посмотрим, какой вид примут первые четыре условия Фаркуса, если мы запишем их не в буквах, а в цифрах.
2 6 4 5
(1). Для любого числа Х число 2X2 является родственным числу X.
(2). Если число X родственно числу Y, то число 6Х оказывается родственным числу 2 У.
(3). Если число X родственно числу У, то число 4Х родственно числу Т.
(4). Если число X родственно числу У, то число 5Х родственно числу УУ.
Сразу видно, что это — точно те же правила, которым подчиняется последняя машина Мак-Каллоха, с той лишь разницей, что вместо слова «порождает» используется слово «родственно». (Конечно, я мог бы воспользоваться словом «порождает» и в гл. 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 и У, если число X порождает число У, число НХ порождало бы число Y2Y2. Если мы сумеем найти это число Н, тогда при любом У число Н2 У2 будет порождать число У2 У2 (потому что, согласно правилу MI, число 2У2 порождает число У), а значит, число Н2Н2 будет порождать число Н2Н2; тем самым мы получим искомое число N. Но как найти число Н?
Эта задача сводится к следующей: как, исходя из заданного числа У и последовательно применяя операции, которые способна выполнять наша машина, получить число У2У2? Так вот, построить число У2У2 из числа У можно следующим способом: сначала построить обращение числа У, получив число У; затем слева от «у» приписать цифру 2, получив тем самым число 2У; далее построить обращение числа 2Т, получив число У2; наконец, построить повторение числа У2, получив число У2 У2. Эти операции обозначаются соответственно операционными числами 4, 6, 4 и 5, поэтому в качестве Н мы выберем число 5464.
Давайте проверим, подходит ли нам найденное число Н. Пусть число X порождает число У; тогда мы должны выяснить, действительно ли число 5464Н порождает число У2У2. Но поскольку X порождает У, то число 4Х порождает число У (в соответствии с правилом MIII); значит, число 64Х порождает число 2V (в соответствии с правилом МII). Отсюда следует, что число 464Х порождает число У2 (в соответствии с правилом MIII), и, стало быть, число 5464Х порождает число У2У2 (в соответствии с правилом MIV). Итак, мы получили, что если X порождает У, то число НХ в самом деле порождает число 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 действительно является родственной самой себе.
Часть четвертая. Разрешима или неразрешима наша задача?
Логическая машина Фергюссона
Через несколько месяцев после того, как была с блеском разрешена загадка банковского сейфа в Монте-Карло, Крейг и Мак-Каллох наконец-то навестили Фергюссона — их очень заинтересовала его логическая машина. Разговор скоро зашел о сущности доказуемости.
— Я расскажу вам интересную и весьма поучительную историю, — сказал Фергюссон. — На экзамене по геометрии одного студента попросили доказать теорему Пифагора. Он сдал свою работу преподавателю, но тот возвратил ее с пометкой: «Это не доказательство!» Молодой человек пошел к преподавателю и сказал: «Сэр, как вы можете утверждать, будто то, что я вам сдал, — не доказательство? За весь курс лекций вы ни разу не дали нам определения доказательства. Вы давали нам строгие определения таких геометрических понятий, как треугольник, квадрат, окружность, параллельность, перпендикулярность и т. д., однако никогда не привели нам точного определения того, что же вы называете доказательством. Как же теперь вы можете так уверенно заявлять, будто мое доказательство — вовсе не доказательство? Как вы можете доказать, что оно не является доказательством?»
— Блестяще! — воскликнул Крейг, захлопав в ладоши. — Этот юноша далеко пойдет. А что же ответил преподаватель?
— К сожалению, — усмехнулся Фергюссон, — преподаватель оказался сухим педантом без чувства юмора и воображения. Он снизил студенту оценку за непочтительность.
— Очень жаль, — с досадой сказал Крейг. — Окажись я на месте преподавателя, непременно поставил бы этому студенту высший балл.
— Разумеется, — согласился Фергюссон, — я бы поступил точно так же. Но вы же прекрасно знаете, как часто преподаватели, лишенные творческого начала, побаиваются способных студентов.
— Должен признаться, — сказал Мак-Каллох, — что на месте этого преподавателя я бы тоже не смог ответить на вопрос студента. Разумеется, я похвалил мы его за толково поставленный вопрос, но ответить на него я бы все-таки не смог. В самом деле, что такое доказательство? Когда я сталкиваюсь с правильным доказательством, я почему-то всегда понимаю, что оно правильно; когда мне попадаются слабые аргументы, я обычно могу их указать. Но если бы меня попросили дать строгое определение доказательства, я тоже оказался бы в весьма затруднительном положении.
— Точно так же, как и почти все работающие математики, — поддержал Мак-Каллоха Фергюссон. — В девяносто девяти процентах случаев они вполне могут распознать правильность доказательства или указать на слабые места в неправильном доказательстве, однако не и состоянии привести точное определение доказательства. Нас же, логиков, интересует прежде всего анализ самого понятия «доказательство» — ведь мы хотим определить его так же строго, как и любое другое математическое понятие.
— Но раз большинство математиков все же понимают, что такое доказательство, хотя и не могут дать его четкого определения, то так ли уж важно искать его? — заметил Крейг.
— Важно, и по нескольким причинам, — ответил Фергюссон. — Но даже не будь этих причин, я все равно котел бы знать это определение ради самого определения. В истории математики часто случалось, что какие-то основные понятия, например понятие непрерывности, интуитивно понимались и осваивались еще задолго до того, как для них было введено строгое определение. Однако, получив четкое определение, данное понятие как бы переходит в новую категорию. Становится возможным установить связанные с ним факты, которые было бы очень трудно или вовсе невозможно открыть, не зная совершенно четко объема этого понятия. В этом смысле не является исключением и понятие «доказательство». Так, иногда случается, что в доказательстве используется какой-нибудь новый принцип — например аксиома выбора — и при этом часто возникает сомнение, является ли применение этого принципа законным. Так вот, строгое определение понятия «доказательство» позволяет точно указать, какие математические принципы можно использовать, а какие нельзя.
— Я расскажу вам интересную и весьма поучительную историю, — сказал Фергюссон. — На экзамене по геометрии одного студента попросили доказать теорему Пифагора. Он сдал свою работу преподавателю, но тот возвратил ее с пометкой: «Это не доказательство!» Молодой человек пошел к преподавателю и сказал: «Сэр, как вы можете утверждать, будто то, что я вам сдал, — не доказательство? За весь курс лекций вы ни разу не дали нам определения доказательства. Вы давали нам строгие определения таких геометрических понятий, как треугольник, квадрат, окружность, параллельность, перпендикулярность и т. д., однако никогда не привели нам точного определения того, что же вы называете доказательством. Как же теперь вы можете так уверенно заявлять, будто мое доказательство — вовсе не доказательство? Как вы можете доказать, что оно не является доказательством?»
— Блестяще! — воскликнул Крейг, захлопав в ладоши. — Этот юноша далеко пойдет. А что же ответил преподаватель?
— К сожалению, — усмехнулся Фергюссон, — преподаватель оказался сухим педантом без чувства юмора и воображения. Он снизил студенту оценку за непочтительность.
— Очень жаль, — с досадой сказал Крейг. — Окажись я на месте преподавателя, непременно поставил бы этому студенту высший балл.
— Разумеется, — согласился Фергюссон, — я бы поступил точно так же. Но вы же прекрасно знаете, как часто преподаватели, лишенные творческого начала, побаиваются способных студентов.
— Должен признаться, — сказал Мак-Каллох, — что на месте этого преподавателя я бы тоже не смог ответить на вопрос студента. Разумеется, я похвалил мы его за толково поставленный вопрос, но ответить на него я бы все-таки не смог. В самом деле, что такое доказательство? Когда я сталкиваюсь с правильным доказательством, я почему-то всегда понимаю, что оно правильно; когда мне попадаются слабые аргументы, я обычно могу их указать. Но если бы меня попросили дать строгое определение доказательства, я тоже оказался бы в весьма затруднительном положении.
— Точно так же, как и почти все работающие математики, — поддержал Мак-Каллоха Фергюссон. — В девяносто девяти процентах случаев они вполне могут распознать правильность доказательства или указать на слабые места в неправильном доказательстве, однако не и состоянии привести точное определение доказательства. Нас же, логиков, интересует прежде всего анализ самого понятия «доказательство» — ведь мы хотим определить его так же строго, как и любое другое математическое понятие.
— Но раз большинство математиков все же понимают, что такое доказательство, хотя и не могут дать его четкого определения, то так ли уж важно искать его? — заметил Крейг.
— Важно, и по нескольким причинам, — ответил Фергюссон. — Но даже не будь этих причин, я все равно котел бы знать это определение ради самого определения. В истории математики часто случалось, что какие-то основные понятия, например понятие непрерывности, интуитивно понимались и осваивались еще задолго до того, как для них было введено строгое определение. Однако, получив четкое определение, данное понятие как бы переходит в новую категорию. Становится возможным установить связанные с ним факты, которые было бы очень трудно или вовсе невозможно открыть, не зная совершенно четко объема этого понятия. В этом смысле не является исключением и понятие «доказательство». Так, иногда случается, что в доказательстве используется какой-нибудь новый принцип — например аксиома выбора — и при этом часто возникает сомнение, является ли применение этого принципа законным. Так вот, строгое определение понятия «доказательство» позволяет точно указать, какие математические принципы можно использовать, а какие нельзя.