Принцесса или тигр   ::   Смаллиан Рэймонд

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

Обсуждение



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

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



Решения



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

— Это верно, — согласился Мак-Каллох.