Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
'1.8. Машины Тьюринга
Каждое устройство M рассмотренного вида характеризуется тем свойством, что объем времени и пространства, которые оно исполь-
Формальные свойства грамматик
153
зует для решения какой-либо отдельной задачи(например, при допущении или отбрасывании определенных входов) является в некотором смысле заранее заданным. В действительности, наиболее глубокие и наиболее далеко идущие математические, исследования в теории автоматов касаются устройств, которые не обладают этим свойством. Такие устройства, называемые машинами Тьюринга, мы теперь коротко рассмотрим.
Мы получим машияу Тьюринга, если возьмем линейно0грани-ченный автомат, заданный в определении 5, и добавим к его правилам пятерки (#, /, А, /, т), где /4=0, имеющие свойства, описанные в определении 5. Эти правила позволяют устройству использовать не ограниченные заранее куски ленты влево и вправо в ііроцсссе вычислений, так как символ # может быть заменен теперь на символ алфавита. Обычно также требуют, чтобы эти устройства были детерминированными в том смысле, что для заданной конфигурации машины-ленты имеется лишь один возможный ход; если (i, jt ^ />т) и (t, I, k', 1', т') являются правилами, то k=k', 1 = 1' и п=т'. Можно сказать, что машина Тьюринга допускает (порождает) цепочку при условиях, в основном аналогичных поставленным выше. А именно МЫ пишем на ленте СИМВОЛЫ цепочки 9 В подряд идущих клетках, а остальную часть бесконечной ленты считаем заполненной символом Мы устанавливаем блок управления в состояние S0 со считывающей головкой, стоящей против самого левого символа чф #. Если устройство проработало до первого возвращения в 5^ то мы говорим, что машина допускает (порождает) <р. Кроме того, последовательность символов, которые теперь стоят на ленте между символами #, образует цепочку ф, которую можно назвать Выходом машины. Мы можем, иначе говоря, рассматривать это устройство как частичную функцию, которая переводит ? в ф при постатейных условиях.
Полученные таким способом устройства своим поведением полностью отличаются от автоматов, рассмотренных в разд. 1.2—1.7. Так, например, не существует общего способа определить по заданному входу, остановится ли устройство или же будет работать до бесконечности. Далее, не существует общего способа определить путем систематического исследования правил устройства, ііак долго оно будет работать, если оно допускает входную цепочку, или какой кусок ленты будет использован, прежде чем будет Получен ответ. He существует единого и систематического способа определения по изучению правил машины Тьюринга, даст ли она вообще когда-нибудь выходной символ, будет ли ее выход (или множество, которое она допускает) конечным или бесконечным; также невозможно в общем случае определить при помощи некоторого практического приема, будут ли два таких устройства выдавать когда-либо одинаковый выход или же допускать одно и то ®е мно-
162
И. Хомский.
Условие 1. Если есть правило G, то существуют не-
нулевые символы а1,...,ат, Ьъ..., Ьп, где т-^п, такие, что ^=O1..-...ати =
Иначе, условие 1 предполагает, что если ?-»-<}> есть правило 6» то не короче ср. Грамматика, удовлетворяющая условию 1, называется грамматикой типа 1.
В дальнейшем для каждого условия і, которое будет выдвигаться, мы будем называть грамматику, удовлетворяющую этому условию, грамматикой типа і, язык, порождаемый грамматикой типа І, мы будем называть языком типа і. Самые общие системы подстановок считаются грамматиками типа 0. Условия, которые мы будем рассматривать, расположены в порядке возрастающей строгости,т.е. для каждого і грамматика типа і+l всегда будет удовлетворять условию для грамматики типа і, но будет такая грамматика типа І, которая не будет удовлетворять условию типа І-И.
Условие 1 налагает существенное ограничение на порождающую способность грамматики. Поскольку для вывода в грамматике типа 1 верно, что каждая строка имеет по меньшей мере такую же длину, как и предыдущая, очевидна следующая теорема.
Теорема8. Каждый язык типа 1 представляет собой рекурсивное множество.
Действительно, если задана G — грамматика типа 1 и цепочка х, то лишь конечное число выводов (тех, последние строки которых не длиннае х) должно быть просмотрено, прежде чем мы решим, порождается ли X грамматикой G. Однако не все рекурсивные языки порождаются грамматиками типа 1, как непосредственно показывает рассуждение диагональным методом1).
Хотя грамматики типа 1 порождают только рекурсивные множества, в некотором смысле они близки к тому, чтобы порождать любые рекурсивно-перечислимые множества. Для простаты рассуждений ограничимся множествами целых положительных чисел (без потери общности), поскольку любое множество конечных цепочек может быть эффективно закодировано множеством целых положительных чисел.
Обратимся снова к описанию машины Тьюринга, данному в разд. 1.8. Рассмотрим машину Тьюринга с алфавитом (1, е), где е — единичный элемент (т.е. клетка, содержащая е, рассматривается как пустая, а замена 1 иа е рассматривается как стирание). Можно предположить, что каждая отдельная машина M работает следующим образом: на входе имеется последовательность Iі,. і>1 (т.е. ( последовательных вхождений 1, окаймленных с обоих сторон бесконечными цепочками символов #). Машина M начинает
