Принцесса или тигр?

Значит, мы можем окончательно сформулировать главную мысль последнего абзаца в таком виде: для любых комбинаций х и у, составленных из четырех букв Q, L, V, R, если, исходя из правил MI, MII, MIII и MIV, используемых в последней машине Мак-Каллоха, можно показать, что число х порождает число у, то тогда, исходя из первых четырех условий Фаркуса, можно показать и то, что комбинация х является родственной по отношению к комбинации у, и наоборот.

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

Но как же нам найти такое число N, которое, порождало бы само себя в нашей последней машине? Прежде всего будем искать некоторое число Н, такое, чтобы для любых чисел X и Y, если число X порождает число Y, число НХ порождало бы число Y2Y2. Если мы сумеем найти это число Н, тогда при любом Y число Н2Y2 будет порождать число Y2Y2 (потому что, согласно правилу MI, число 2Y2 порождает число Y), а значит, число Н2Н2 будет порождать число Н2Н2; тем самым мы получим искомое число N. Но как найти число Н?

Эта задача сводится к следующей: как, исходя из заданного числа Y и последовательно применяя операции, которые способна выполнять наша машина, получить число Y2Y2? Так вот, построить число Y2Y2 из числа Y можно следующим способом: сначала построить обращение числа Y, получив число Y⃖; затем слева от Y⃖ приписать цифру 2, получив тем самым число 2Y⃖; далее построить обращение числа 2Y⃖, получив число Y2; наконец, построить повторение числа Y2, получив число Y2Y2. Эти операции обозначаются соответственно операционными числами 4, 6, 4 и 5, поэтому в качестве Н мы выберем число 5464.

Давайте проверим, подходит ли нам найденное число Н. Пусть число X порождает число Y; тогда мы должны выяснить, действительно ли число 5464Н порождает число Y2Y2. Но поскольку X порождает Y, то число 4X порождает число Y⃖ (в соответствии с правилом MIII); значит, число 64X порождает число 2Y⃖ (в соответствии с правилом МII). Отсюда следует, что число 464X порождает число Y2 (в соответствии с правилом MIII), и, стало быть, число 5464X порождает число Y2Y2 (в соответствии с правилом MIV). Итак, мы получили, что если X порождает Y, то число НХ в самом деле порождает число 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 действительно является родственной самой себе.

Часть четвертая. Разрешима или неразрешима наша задача?

14. Логическая машина Фергюссона

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