Решения

Рассмотрим сначала произвольную машину, которая подчиняется правилам 1 и 4. Как известно, при любом X число 52X порождает число XX; поэтому если выбрать в качестве X число 52, то мы получим, что число 5252 порождает число 5252. Итак, у нас есть число, которое порождает само себя. Кроме того, число 552552 порождает повторение самого себя. Далее, чтобы для любого А найти число X, которое порождает АХ, возьмем в качестве X число 52А52 (в самом деле, оно порождает повторение числа А52, которое есть число A52A52, то есть число АХ). Тем самым мы доказали теорему 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. Для заданного операционного числа M числом А, порождающим М(X), оказывается число М52М52. (Сравните его с прежним решением — числом М32МЗ, полученным для машины, в которой вместо правила 4 используется правило 2.) Если теперь задано операционное число M и некое число А, то числом X, порождающим M(AX), будет число М52АМ52. (Сравните его с прежним решением — М32АМЗ.) Построенные решения показывают нам, что оба принципа Крейга могут быть получены на основании правил 1 и 4. Впрочем, я сформулировал гораздо более общее утверждение, а именно: для того чтобы получить принципы Крейга, достаточно одного только закона Мак-Каллоха (теорема 2). Это утверждение можно доказать тем же способом, который использовался нами в гл. 10. В самом деле, для любого заданного операционного числа M существует некое число Y, которое порождает MY; отсюда ясно, что число MY порождает М(МY). Поэтому число X порождает М(X), где X = MY. Точно так же для любого числа А, если имеется некоторое число Y, порождающее AMY, число MY порождает М(АMY) и, следовательно, число X порождает М(АХ) при X = MY.

Что же касается теоремы 3, то ее можно доказать так же, как это делалось в предыдущей главе. [Например, если даны операционные числа M и N и если выполняется второй принцип Крейга, то существует некое число X, которое порождает M(N2X). Если теперь мы обозначим число N2X через Y, то получим, что число X порождает М(Y), а число Y порождает N(X).]