Это означает, что, как бы мы ни расширяли первую машину Мак-Каллоха, вводя в нее новые правила, работа результирующего устройства все равно будет подчиняться принципу Крейга (а фактически обоим его принципам).
Первый принцип Крейга связан с одним из знаменитых результатов теории вычислимых функций, известным под названием теоремы о рекурсии (или, как ее иногда называют, теоремы о неподвижной точке). С помощью правил 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. Может, с помощью сравнения соответствующих относительных длин? Нет, для доказательства свойств, относящихся к нынешней машине, метод сравнения относительных длин оказывается слишком громоздким. Как будет показано в конце этой главы, решение было найдено именно с помощью принципа Крейга.
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.
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 — для получения повторения, 4 — для получения обращения и 3 — для получения ассоциата); решением в данном случае является число 543325433. (Читатель может легко удостовериться непосредственно, что число 543325433 действительно порождает повторение обращения ассоциата числа 543325433.)
Для решения второй задачи Мак-Каллоха (найти число X, которое порождает ассоциат повторения обращения X) возьмем в качестве М число 354;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
Первый принцип Крейга связан с одним из знаменитых результатов теории вычислимых функций, известным под названием теоремы о рекурсии (или, как ее иногда называют, теоремы о неподвижной точке). С помощью правил 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. Может, с помощью сравнения соответствующих относительных длин? Нет, для доказательства свойств, относящихся к нынешней машине, метод сравнения относительных длин оказывается слишком громоздким. Как будет показано в конце этой главы, решение было найдено именно с помощью принципа Крейга.
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.
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 — для получения повторения, 4 — для получения обращения и 3 — для получения ассоциата); решением в данном случае является число 543325433. (Читатель может легко удостовериться непосредственно, что число 543325433 действительно порождает повторение обращения ассоциата числа 543325433.)
Для решения второй задачи Мак-Каллоха (найти число X, которое порождает ассоциат повторения обращения X) возьмем в качестве М число 354;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52