В первом случае я называю число X отмирающим относительно данной конкретной машины, во втором случае число X я называю вечным. Конечно, любое число может быть отмирающим для одной машины и вечным для другой.
— Давай возьмем твою первую машину, — предложил Крейг. — Я могу придумать кучу отмирающих чисел, а не можешь ли ты привести мне пример вечного числа?
— Ну хотя бы число 323,— ответил Мак-Каллох. — Ведь число 323 порождает самое себя и поэтому, сколько бы раз я не вводил его в машину, я всегда буду получать 323. Так что в данном случае процесс явно оказывается бесконечным.
— А ведь верно! — засмеялся Крейг. — Ну хорошо, а существуют ли другие вечные числа?
1. —Тогда, — продолжал Мак-Каллох, — что ты скажешь по поводу числа 3223? Отмирающее оно или вечное?
2. — А как насчет числа 32223? — спросил Фергюссон. — Оно для вашей первой машины — отмирающее или вечное?
Мак-Каллох на некоторое время задумался.
— Это не так трудно определить, — ответил он наконец — Однако я думаю, вам будет интересно разобраться в этом самому.
3. —Можете попробовать еще число 3232,—в свою очередь предложил Мак-Каллох, — попытайтесь определить— отмирающее оно или вечное.
4 — А если взять число 32323? — спросил Крейг. — Отомрет оно или нет?
5 — Все это очень интересно, — сказал Мак-Каллох, — но я еще не добрался до самого главного. А дело вот в чем: один мой приятель придумал весьма хитроумную числовую машину. Он утверждает, будто его машина может выполнять любые операции, на которые только способна числовая машина вообще. Мой друг назвал ее универсальной машиной. И вот оказывается, что есть несколько таких чисел, про которые ни я, ни он не можем сказать—отмирающие они или вечные. Поэтому мне хотелось бы разработать какой-нибудь чисто механический тест, чтобы определять, какие числа отмирающие, а какие — вечные. Правда, пока У меня ничего не выходит. Конкретнее, я пытаюсь найти такое число Н, которое для любого приемлемого числа X давало бы вечное число НХ, если X — отмирающее, и отмирающее число НХ, если X—вечное. Если бы мне это удалось, то я сразу смог бы определить, отмирающее ли или вечное любое приемлемое число X.
— А как именно это определить с помощью числа Н? — спросил Крейг.
— Если бы я нашел число Н, — объяснил Мак — Каллох, — то сначала построил бы такую же машину, как у моего приятеля. Потом, взяв произвольное приемлемое число X, я ввел бы его в одну из машин; одновременно мой приятель ввел бы число НХ в другую машину. Понятно, что описанный процесс может прекратиться только в одной из машин; если это произойдет в моей машине, я буду знать, что число X — отмирающее; если в машине моего приятеля, то я сразу пойму, что число X — вечное.
— Да ведь вам незачем строить вторую машину, — сказал Фергюссон. — Это можно сделать и на одной машине, просто переключая ее с одного процесса на другой.
— Верно, — согласился Мак-Каллох. — Но только все это пустые рассуждения, пока я не сумел найти число Н. Вполне возможно, что моя машина просто не способна решить задачу о своей собственной «выживаемости», то есть, я хочу сказать, что, быть может, такого числа Н вообще не существует. А может, это я не способен найти такое число. Вот эту то проблему, джентльмены, я и хотел бы обсудить вместе с вами.
— Ну что ж, — сказал Фергюссон, — прежде всего мы должны знать, по каким правилам работает данная машина.
— Всего в ней используется 25 правил, — начал было Мак-Каллох. — Первые два из них — те же самые, что и в моей первой машине.
— Минуточку, — прервал его Фергюссон. — Вы хотите сказать, что машина вашего приятеля подчиняется правилам 1 и 2?
— Вот именно, — ответил Мак-Каллох.
— Тогда мне все ясно, — заявил Фергюссон. — Ни одна машина, в которой действуют правила 1 и 2, не может решить задачу о своей собственной «выживаемости».
— Как же вы сумели так быстро об этом догадаться? — спросил Крейг.
— Я уже сталкивался с подобного рода вещами, — объяснил Фергюссон. — Не так давно в моей работе возникла аналогичная проблема.
И все же, как именно Фергюссон определил, что машина, подчиняющаяся правилам 1 и 2, не может решить задачу о своей собственной «выживаемости»?
Решения
1. Напомним, что число 3223 порождает число 23223, а число 23223 в свою очередь порождает число 3223. Значит, у нас есть два числа, 3223 и 23223, которые порождают друг друга. Отсюда следует, что оба они вечны: ведь если ввести в машину одно из них, то получится второе, а если ввести второе, то получится первое. Ясно, что такой процесс бесконечен.
2. Возьмем два любых числа X и У. Мы будем говорить, что число X приводит к числу У, если X порождает У, или если X порождает какое-то число, которое порождает У, или если X порождает какое-то число, которое порождает другое число, которое в свою очередь порождает У, и т. д. Иначе говоря, если, введя в машину число X, мы на каком-то этапе нашего процесса получим число У, то будем говорить, что число X приводит к числу У. Так, например, число 22222278 приводит к числу 78 фактически на шестом этапе. В более общем виде: если число Т представляет собой произвольную цепочку двоек, то для любого числа X число ТХ в конце концов приводит к X.
Далее, число 32223 не порождает самое себя, но приводит к самому себе, потому что оно порождает число 2232223, которое порождает затем число 232223, а это число в свою очередь вновь порождает 32223. Но раз число 32223 приводит к самому себе, то, стало быть, оно должно быть вечным.
Читатель, по-видимому, уже обратил внимание на следующую закономерность: если число Т состоит целиком из одних двоек, то число ЗТЗ должно приводить к самому себе и, следовательно, будет вечным.
3. Мне известен только один способ решения этой задачи: доказать в общем виде, что если число Т состоит целиком из одних двоек, то число ЗТ32 вечно и, следовательно, частный его случай — число 3232 — тоже является вечным. Этот факт служит иллюстрацией некоторого еще более общего принципа, который используется нами в решении следующей задачи.
Предположим, что у нас имеется определенный класс чисел (неважно, конечный или бесконечный), причем такой, что каждое число из этого класса приводит к некоторому числу из этого же класса (либо к самому себе, либо к другому числу). Тогда все числа, входящие в этот класс, должны быть вечными.
Попробуем воспользоваться этим принципом применительно к нашей задаче. Рассмотрим класс чисел вида ЗТ32, где Т — произвольная цепочка двоек. Покажем, что число ЗТ32 должно приводить к другому числу из этого же класса.
Возьмем сначала число 3232. Оно порождает число 32232, то есть элемент того же класса. Теперь, что нам дает число 32232? Оно порождает число 2322232, которое в свою очередь порождает число 322232, то есть элемент того же класса. А что получается с числом 322232? Оно порождает число 223222232, которое порождает число 23222232, а оно в свою очередь дает нам число 3222232, так что мы опять возвращаемся в указанный класс. В более общем виде: для любой цепочки двоек Т число 32Т32 порождает число Т322Т32, которое приводит к числу 322Т32, опять представляющему собой элемент данного класса. Итак, все числа, входящие в указанный класс, являются вечными.
4. Число 32323 порождает число 3232323, которое порождает число 32323232323, а это последнее в свою очередь порождает число 3232323232323232323. Дальнейшая схема представляется очевидной: любое число, состоящее из повторенного несколько раз числа 32 с тройкой на конце, порождает другое число того же вида (только более длинное), причем все эти числа будут вечными.
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
— Давай возьмем твою первую машину, — предложил Крейг. — Я могу придумать кучу отмирающих чисел, а не можешь ли ты привести мне пример вечного числа?
— Ну хотя бы число 323,— ответил Мак-Каллох. — Ведь число 323 порождает самое себя и поэтому, сколько бы раз я не вводил его в машину, я всегда буду получать 323. Так что в данном случае процесс явно оказывается бесконечным.
— А ведь верно! — засмеялся Крейг. — Ну хорошо, а существуют ли другие вечные числа?
1. —Тогда, — продолжал Мак-Каллох, — что ты скажешь по поводу числа 3223? Отмирающее оно или вечное?
2. — А как насчет числа 32223? — спросил Фергюссон. — Оно для вашей первой машины — отмирающее или вечное?
Мак-Каллох на некоторое время задумался.
— Это не так трудно определить, — ответил он наконец — Однако я думаю, вам будет интересно разобраться в этом самому.
3. —Можете попробовать еще число 3232,—в свою очередь предложил Мак-Каллох, — попытайтесь определить— отмирающее оно или вечное.
4 — А если взять число 32323? — спросил Крейг. — Отомрет оно или нет?
5 — Все это очень интересно, — сказал Мак-Каллох, — но я еще не добрался до самого главного. А дело вот в чем: один мой приятель придумал весьма хитроумную числовую машину. Он утверждает, будто его машина может выполнять любые операции, на которые только способна числовая машина вообще. Мой друг назвал ее универсальной машиной. И вот оказывается, что есть несколько таких чисел, про которые ни я, ни он не можем сказать—отмирающие они или вечные. Поэтому мне хотелось бы разработать какой-нибудь чисто механический тест, чтобы определять, какие числа отмирающие, а какие — вечные. Правда, пока У меня ничего не выходит. Конкретнее, я пытаюсь найти такое число Н, которое для любого приемлемого числа X давало бы вечное число НХ, если X — отмирающее, и отмирающее число НХ, если X—вечное. Если бы мне это удалось, то я сразу смог бы определить, отмирающее ли или вечное любое приемлемое число X.
— А как именно это определить с помощью числа Н? — спросил Крейг.
— Если бы я нашел число Н, — объяснил Мак — Каллох, — то сначала построил бы такую же машину, как у моего приятеля. Потом, взяв произвольное приемлемое число X, я ввел бы его в одну из машин; одновременно мой приятель ввел бы число НХ в другую машину. Понятно, что описанный процесс может прекратиться только в одной из машин; если это произойдет в моей машине, я буду знать, что число X — отмирающее; если в машине моего приятеля, то я сразу пойму, что число X — вечное.
— Да ведь вам незачем строить вторую машину, — сказал Фергюссон. — Это можно сделать и на одной машине, просто переключая ее с одного процесса на другой.
— Верно, — согласился Мак-Каллох. — Но только все это пустые рассуждения, пока я не сумел найти число Н. Вполне возможно, что моя машина просто не способна решить задачу о своей собственной «выживаемости», то есть, я хочу сказать, что, быть может, такого числа Н вообще не существует. А может, это я не способен найти такое число. Вот эту то проблему, джентльмены, я и хотел бы обсудить вместе с вами.
— Ну что ж, — сказал Фергюссон, — прежде всего мы должны знать, по каким правилам работает данная машина.
— Всего в ней используется 25 правил, — начал было Мак-Каллох. — Первые два из них — те же самые, что и в моей первой машине.
— Минуточку, — прервал его Фергюссон. — Вы хотите сказать, что машина вашего приятеля подчиняется правилам 1 и 2?
— Вот именно, — ответил Мак-Каллох.
— Тогда мне все ясно, — заявил Фергюссон. — Ни одна машина, в которой действуют правила 1 и 2, не может решить задачу о своей собственной «выживаемости».
— Как же вы сумели так быстро об этом догадаться? — спросил Крейг.
— Я уже сталкивался с подобного рода вещами, — объяснил Фергюссон. — Не так давно в моей работе возникла аналогичная проблема.
И все же, как именно Фергюссон определил, что машина, подчиняющаяся правилам 1 и 2, не может решить задачу о своей собственной «выживаемости»?
Решения
1. Напомним, что число 3223 порождает число 23223, а число 23223 в свою очередь порождает число 3223. Значит, у нас есть два числа, 3223 и 23223, которые порождают друг друга. Отсюда следует, что оба они вечны: ведь если ввести в машину одно из них, то получится второе, а если ввести второе, то получится первое. Ясно, что такой процесс бесконечен.
2. Возьмем два любых числа X и У. Мы будем говорить, что число X приводит к числу У, если X порождает У, или если X порождает какое-то число, которое порождает У, или если X порождает какое-то число, которое порождает другое число, которое в свою очередь порождает У, и т. д. Иначе говоря, если, введя в машину число X, мы на каком-то этапе нашего процесса получим число У, то будем говорить, что число X приводит к числу У. Так, например, число 22222278 приводит к числу 78 фактически на шестом этапе. В более общем виде: если число Т представляет собой произвольную цепочку двоек, то для любого числа X число ТХ в конце концов приводит к X.
Далее, число 32223 не порождает самое себя, но приводит к самому себе, потому что оно порождает число 2232223, которое порождает затем число 232223, а это число в свою очередь вновь порождает 32223. Но раз число 32223 приводит к самому себе, то, стало быть, оно должно быть вечным.
Читатель, по-видимому, уже обратил внимание на следующую закономерность: если число Т состоит целиком из одних двоек, то число ЗТЗ должно приводить к самому себе и, следовательно, будет вечным.
3. Мне известен только один способ решения этой задачи: доказать в общем виде, что если число Т состоит целиком из одних двоек, то число ЗТ32 вечно и, следовательно, частный его случай — число 3232 — тоже является вечным. Этот факт служит иллюстрацией некоторого еще более общего принципа, который используется нами в решении следующей задачи.
Предположим, что у нас имеется определенный класс чисел (неважно, конечный или бесконечный), причем такой, что каждое число из этого класса приводит к некоторому числу из этого же класса (либо к самому себе, либо к другому числу). Тогда все числа, входящие в этот класс, должны быть вечными.
Попробуем воспользоваться этим принципом применительно к нашей задаче. Рассмотрим класс чисел вида ЗТ32, где Т — произвольная цепочка двоек. Покажем, что число ЗТ32 должно приводить к другому числу из этого же класса.
Возьмем сначала число 3232. Оно порождает число 32232, то есть элемент того же класса. Теперь, что нам дает число 32232? Оно порождает число 2322232, которое в свою очередь порождает число 322232, то есть элемент того же класса. А что получается с числом 322232? Оно порождает число 223222232, которое порождает число 23222232, а оно в свою очередь дает нам число 3222232, так что мы опять возвращаемся в указанный класс. В более общем виде: для любой цепочки двоек Т число 32Т32 порождает число Т322Т32, которое приводит к числу 322Т32, опять представляющему собой элемент данного класса. Итак, все числа, входящие в указанный класс, являются вечными.
4. Число 32323 порождает число 3232323, которое порождает число 32323232323, а это последнее в свою очередь порождает число 3232323232323232323. Дальнейшая схема представляется очевидной: любое число, состоящее из повторенного несколько раз числа 32 с тройкой на конце, порождает другое число того же вида (только более длинное), причем все эти числа будут вечными.
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