|
— Верно,— согласился Мак-Каллох.— Но только все это пустые рассуждения, пока я не сумел найти число Н. Вполне возможно, что моя машина просто не способна решить задачу о своей собственной «выживаемости», то есть, я хочу сказать, что, быть может, такого числа Н вообще не существует. А может, это я не способен найти такое число. Вот эту то проблему, джентльмены, я и хотел бы обсудить вместе с вами. - Ну что ж,— сказал Фергюссон,— прежде всего мы должны знать, по каким правилам работает данная машина. — Всего в ней используется 25 правил,— начал было Мак-Каллох.— Первые два из них—те же самые, что и в моей первой машине. - Минуточку,— прервал его Фергюссон.— Вы хотите сказать, что машина вашего приятеля подчиняется правилам 1 и 2? — Вот именно,— ответил Мак-Каллох. - Тогда мне все ясно,— заявил Фергюссон.— Ни одна машина, в которой действуют правила 1 и 2, не может решить задачу о своей собственной «выживаемости». Стр. 204 — Как же вы сумели так быстро об этом догадаться?— спросил Крейг. — Я уже сталкивался с подобного рода вещами,— объяснил Фергюссон.— Не так давно в моей работе возникла аналогичная проблема. И все же, как именно Фергюссон определил, что машина, подчиняющаяся правилам 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 приводит к самому себе, то, стало быть, оно должно быть вечным. — 127 —
|