Минский М.
ВЫЧИСЛЕНИЯ И АВТОМАТЫ
*** 1971 ***
|
ФPAГMEHT КНИГИ (...) Если мы можем установить справедливость этого утверждения, то отсюда следует неразрешимость общей проблемы соответствия, так как любую проблему останова'1 машины Тьюринга можно рассматривать как вопрос о том, достигнет ли рассматриваемая машина некоторого специального состояния при чистой ленте. Далее в случае нормальной системы это можно свести к вопросу об окончании работы системы на некотором конкретном слове Z. (Кроме того, можно просто свести это к неразрешимой проблеме остановки для таг-систем.)
Почему справедливо указанное утверждение? Прежде всего укажем, для чего нужны буквы X и Y. Буквы X нужны для того, чтобы была уверенность в том, что если вообще существует подходящая пара, то она должна начинаться с записи ХА аксиомы А. Это гарантируется тем, что если слово Н начинается с X, то оно обязательно начинается с ХАН0, а так как все слова G должны начинаться с X, мы можем быть уверены, что любой подходящий набор начинается с ХА. Аналогично любая подходящая пара слов должна заканчиваться записью Z, или, более точно, должна заканчиваться ZXY, так как в конце слова G не может стоять X, а в конце слова Н могут быть только X или Y. Отсюда следует, что если вообще имеется какое-либо решение проблемы соответствия, то это должно быть слово, представленное в одной из двух форм: (...) Но если это так, то за последовательностью букв Gi стоит в точности такая же последовательность, которая возникает при работе исходной однородной нормальной системы (gi,h{)\ Мы можем доказать это по индукцищ Мы уже убедились в том, ято слово Н должно начинаться с ХА. Тогда слово G должно начинаться с Go. Почему? Потому что система однородна! Это означает, что в качестве начала аксиомы А подходит лишь g0. Но в таком случае go определяет ho — слово, которое должнр быть добавлено к А, — и позволяет нам исключить начальное Go. Следовательно, в качестве начала остающейся части слова подходит лишь G{ . Это означает, что на следующем шаге нормальная система применит продукцию к g, . Тогда Glt определяет Ht — слово, которое должно быть добавлено к тому, что останется после исключения G* из начальной части слова. Затем опять определяется Gti, поскольку система однородна, и это слово должно быть в точности посылкой продукции, которую нормальная система будет использовать на следующем шаге. Таким образом, последовательность Gj должна быть точно такой же, как последовательность gu лежащих в основании однородной нормальной системы (и, следовательно, должна соответствовать шагам вычислений машины Тьюринга). Если процесс заканчивается, то за последним Gu которое было использовано, следует Z, т. е. то, что по определению останется тогда, когда уже нельзя будет применить ни одну продукцию. Следовательно, если слова соответствуют друг другу, то оба они должны представлять собой последовательность, о которой говорится в нашем утверждении. До сих пор единственными однородными нормальными системами, которые мы рассматривали, были таг-системы. Однако мы могли бы, более непосредственно используя теорему 14.1.1, показать, что однородные нормальные системы универсальны. Рассмотрим произвольную машину с двумя регистрами. Будем представлять ее состояния словом в форме (...) Прибавление ко второму регистру Задача. Сможете ли вы сделать подобные построения для случая трех или более регистров? 14.8. МАЛЫЕ УНИВЕРСАЛЬНЫЕ МАШИНЫ ТЬЮРИНГА Существование универсальных машин достаточно удивительно само по себе, но еще более поразительно то, что такие машины могут иметь весьма простую структуру. Может возникнуть вопрос: насколько малыми могут быть такие машины? Но для того, чтобы ответить на него, прежде всего нужно иметь некоторую меру величины или сложности машины. Шеннон [92] предложил рассматривать в качестве такой меры произведение числа символов и числа состояний, поскольку, как он показал, это произведение является в некотором смысле инвариантным. Перестановка состояний и изменение символов не слишком сильно влияют на величину этого произведения. В этом разделе'мы опишем машину Тьюринга с наименьшим известным до настоящего времени произведением числа состояний на числа символов. Эта машина является самым последним результатом «соревнования», начатого Икено [35], который предложил конструкцию машины с шестью символами и десятью состояниями (6,10), Ватанабе [103] — (6, 8), Минским [61] — (6, 7), Ватанабе [104]— (5,8), Минским [62]— (6,6), и, наконец, в работе Минского [63] была предложена машина с четырьмя символами и семью состояниями (4,7), описываемая в этом разделе. Будет принято, что читатель включится в это соревнование (я полагаю, что одна из машин с (3, 6) может быть универсальной, но не могу доказать этого), хотя нужно отчетливо понимать, что этот вопрос является очень сложной головоломкой, но не представляет серьезного математического интереса. Для того чтобы увидеть, насколько изощренные приемы могут здесь потребоваться, читатель может ознакомиться с машиной (6,6), описанной в моей статье [63]. Эта машина гораздо сложнее, чем машина, описываемая в этом разделе. 14.8.1. Универсальная машина с четырьмя символами и семью состояниями Само понятие универсальной машины Тьюринга связано -с понятием описания. Машина, которая моделируется, должна быть описана на ленте универсальной машины в виде некоторого кода. Один из способов такого описания состоит в том, чтобы почти буквально записать на ленте универсальной машины пятерки моделируемой машины. Именно так мы и поступали, описывая машину в гл. 7. С другой стороны, описание в виде пятерок не имеет каких-либо особых преимуществ, и, может быть, другой способ описания позволит построить более простую универсальную машину. Тем не менее мы не должны заходить слишком далеко в этом направлении, так как если допустить возможность проведения вычислений произвольных частично-рекурсивных функций с целью их кодирования и допустить, чтобы код зависел от исходных данных, то в качестве кода можно использовать результаты самих вычислений машины Тьюринга. Но это можно было бы рассматривать как мошенничество. (Это привело бы к машине (2,0) так как ответ мог бы быть записан на ленте в единичном коде, и не требовалось бы никакой вычислительной части.) Поэтому мы введем правило, согласно которому для осуществления кодирования нельзя использовать ничего подобного полному проведению вычислений. Говоря содержательно, это будет гарантировано, если кодирование производится отдельно для структуры машины и для данных. В этом случае мы можем быть уверены, что в процессе кодирования машина не была приспособлена к конкретным данным. Условие, которое мы выдвинули, объясняет то, что мы будем делать ниже. Более формально, можно было бы, например, потребовать, чтобы процесс кодирования представлял собой примитивно-рекурсивную операцию манипулирования символами на входе; это также гарантировало бы нам, что если машина получилась бы универсальной, то это произошло бы не благодаря специальным приемам, использованным в процессе кодирования. Этот вопрос рассматривается в работе Девиса [15]. Сначала мы опишем кодирование для нашей машины, а затем — ее таблицу переходов для состояний и символов. Машина с четырьмя символами и семью состояниями будет действовать путем моделирования произвольной таг-системы (с Р — 2). Согласно теореме 14.6.1, машина, способная это делать, должна быть универсальной. Из доказательства теоремы 14.6.1 мы знаем, что представление пятерок любой машины Тьюринга в виде таг-системы с Р — 2 связано с длительной, но тривиальной процедурой. Поскольку для любого такого представления можно заранее оценить объем требуемой работы, переход является примитивно-рекурсивной операцией. Для каждой пятерки требуется записать 16 продукций.
От нас: 500 радиоспектаклей (и учебники)
|
| ☭ Борис Карлов 2001—3001 гг. ☭ |
