Гладкий - Формальные грамматики и языки - 1973 (947381), страница 9
Текст из файла (страница 9)
упражнения !.10 и !.11). Будем называть Э-машину М дете р м и ни рова ни о й (ДЭ-м а ш и н о й), если ее программа удовлетворяет следующим двум условиям: (а) она не содержит двух различных инструкций с одинаковыми левыми частями; (б) если некоторое состояние содержится в левой части инструкции одного из типов (!) — (ч), то оно не может содержаться в левой части инструкции другого типа.
ДЭ-машина для всякой входной цепочки х имеет не более одного полного х-вычислення. Мы будем говорить, что ДЭ-машина, допускающая Е, о з н а е т этот язык, если для любой це- язык, расп н нечное почки х в о входном алфавите она имеет лишь ко множество х-вычислений (попросту говоря, е аботать с произвольной цепочкой на входной ленте, ра о машина в конце концов останавливае шая язык ДЭ-машина существует тогда и только тогда, когда этот язык рекурсивен (см, ниже, замечание к уп- ражнению 1.22, б)).
Пусть М вЂ” Э-машина с входным алфавитом У и ра- бочим алфавитом ]У. Назовем Э-машину Я с рабочим алфавитом Ф ~У [) !)т()(й) (йфУ() Я7) прямой одно- ленточ ной моделью (п.о. м.) машины М, если ]-вычисленне машины М существует тогда и тогда, когда в машине Я из ситуации (дь, ~~4, 4р хй) достижима ситуация вида (уб Л, 4~$, 4~ х, йу) ГДЕ д1 ЕН 444. Л е м м а 1.5. Для любой Э-машины можно по- строить ее и. о. м.
Если при этом исходная машина де- терминир ни ованная, то и и. о. м. можно сделать детерми- нированнои, Доказательство. Принцип работы Я может быть таким: во «входной зоне» (левее ) н «р й) и «абачей зо- не» (правее й) рабочей ленты Я функционирует точно так же, как М на входной и рабочей лентах соответ- ственно, но всякий раз, когда М переходит от «входно- го» шага к «рабочему» или наоборот, рабочая головка Я б дет передвигаться из зоны в зону, преде тем ячей- варител тельно поставив в обозревавшейся перед ке метку, чтобы найти эту ячейку по возвращении. Ясн, о, что свойство детерминированности, если машина М им обладает, при таком преобразовании сохраняется. Теорема 1.2, Для любой Э-машины М можно по- строить ДЭ-машину М1 такую, что Е(М1) = Е(М).
Дока за тельство. Пусть Р = (с1, ..., с„) — мно- жество символов, ов, находяшееся во взаимно однозначном соответствии с программой машины М. Построим ДЭ- машину М1 с входным алфавитом У и рабочим алфави- том, содержащим У [) ]Р' [) Р 1) (4(, е, [), где У, !У вЂ” соот- ветственно входной н рабочий алфавиты машины М и с(, е, [~ У [) ]У [) Р, работающую следующим образом. Начиная работать в начальной х-ситуации, М1 прежде 47 машины тьюгннгк основные понятия 1гл.
> 46 $>л1 всего переписывает х на рабочую ленту, приписывает справа с([с,е, передвигает рабочую головку на граничный маркер и переходит в некоторое специальное состояние д'. Дальнейшая работа М> состоит в последовательном выполнении «макрошагов», которые могут быть описаны следующим образом. Перед началом «макро- шага» машина находится в ситуации (д', ~х, ~, Л, ~$хЩе), где л — некоторая цепочка в алфавите Р.
При выполнении «макрошага» М„функционирует на участке ленты между ~ и началом 2, как описанная в доказательствелеммы1.5 п.о.м. машины М, однакостойразницей, что она производит при этом не любые «М-шаги», а такие, в результате которых получается «М-вычисление» с шифром Я. Для этого головка перед каждым «М-шагом» передвигается вправо до символа сь стоящего непосредственно вслед за ), «перетаскивает» 1 вправо через этот символ, затем возвращается в ячейку, где следует выполнять очередной «М-шаг» (эта ячейка, разумеется, должна быть ранее помечена), и выполняет его, следуя той инструкции, которая отвечает символу сь если эта инструкция применима. Если же она неприменима, то ) «перетаскивается» влево, пока не окажется перед первым символом цепочки с; эта последняя заменяется цепочкой, непосредственно следующей за ней в смысле некоторого, раз навсегда фиксированного стандартного порядка на Р"; участок ленты между с( и 1 («рабочая зона») уничтожается; метка, имеющаяся на одном из символов цепочки х„стирается; рабочая головка становится на граничный маркер, и машина переходит в состояние д', после чего выполняется следующий «макрошаг».
Если машине удалось «протащить» символ ) через всю цепочку л (так что он оказался непосредственно перед е), то различаются два случая. а) Если имитированное на данном «макрошаге» х-вычисление машины М с шифром с является полным, то рабочая лента уничтожается и машина останавливается, перейдя в состояние, сигналнзирующее об успешном окончании работы, — цепочка х допущена, б) В противном случае дальнейшие действия таковы же, как в рассмотренном выше случае столкновения с неприменимой инструкцией, о машина М; имитирует все х-вычисления Возможност обежсчит сл чае будет работать вечно. озможн рабочим ал множестве множества определенная на нек р м некого ом подм 17" и принимающа я значения также из ф 1 если [х, у1-вывычисляет ункцию б У' сущсст ует числение машины М д М лялюыхх, й Э- г а когда у = х, но построить ДЭ-ма- 1.3. а Для всяко ля>ощси некотоРу у ю нкцшо, можно ю множество значен М пост вить ДЭ-ма- Э-машины можно б) Д я всяк шину, вычисляющую функцию с мно (.(М).
а, П сть ДЭ-машина М с Доказательство. а уст ом и абочим ал авитом М б . Построим Э-машину на " писывается произвольна абочей ленте зап таин сначала на р а г ~ ~" и к ней приписы б е оказывается запнсан- М, после чего н р б 1'(г) пределена; в про,,г если только о ной цепочка г ; затем входная це- тивном случае > р М аботает вечно; з лась) сравнивается с й,'( ); х = Цг), и только в этом я о этого не читала та ничтожается„и машина пере й, г; если окажется х = г, ехо- случае, рабочая лента уничтожа „ е ьное состояние, спо, чт й [. Остается воспользовать- как аз раз множество значений .
стает кото ая сначала переписывает 1.2. б очк на рабочую ленту, затем М конец в случае спешает «разграничитель» с( й машины и, на р я аботы уничтожае будет вычислять функцию, приннма для любого х ение между Э-машииаВыясним теперь взаимоотношени ми и грамматиками, ь!А1 МАШИНЫ ТЬЮРИНГА 49 1Гл. 1 ОСНОВНЫЕ ПОНЯТИЯ 48 Будем говорить, что грамматика Г и Э-машина М эквивалентны, если 1.(Г) = 1,(М).
Аналогично определяется эквивалентность двух Э-м аш ин. Теорем а 1.4. а) Для всякой Э-машины можно построить эквивалентную ей грамматику. б) Для всякой грамматики можно построить эквивалентнию ей Э-машину. Доказательство. а) Пусть М вЂ” данная Э-машина с входным алфавитом И и М! — ее и.о.м. По М, легко построить машину Мь имеющую такие два состояния с)' и д", что при х ен 'ьг" из ситуации(д', Л, ~ф ф, Л, чр х) тогда и только тогда достижима ситуация (д", Л, ~фф, Л, чр), когда хан 1.(М). Построим теперь грамматику Г следующим образом. 1) Основной словарь Г есть )г. 2) Вспомогательный словарь Г есть ())) — 1') и гг' () (1), где ))У и !',! — соответственно рабочий алфавит и множество состояний машины М, и 1ф )г () В' () 1,"с 3) Начальный символ Г есть 1.
4) Схема Г состоит из правил 1- чр а, чрс)'- Л и правил, определенным образом сопоставляемых инструкциям машины Мз, а именно: каждой инструкции бд«- г)б типа (В) сопоставляется правило с)з- бд„; каждой инструкции д -+. баз типа (51) — правило бдв-ьд„; каждой инструкции д — дв Л типа (1у) — всевозможные правила вида дбу- уд«, где у ~ )р', и каждой инструкции вида д„- да П типа (у) — всевозможные правила вида у!)а- д у, где у~%'. Таким образом, схема грамматики Г представляет собой «обращение» программы Мя; поэтому, 'какова бы ни была цепочка хеи )г', в грамматике Г тогда и только тогда можно вывести Чр д'х из Чр д", или, что то же самое, х из 1, когда в М, ситуация (д", Л, Чр ф, Л, ~Ф) достижима из (а', Л, ~ф ф, Л, ф~ х), Отсюда 1.(Г) = 1.(М). б) Пусть Г = (У, У, 1, )с) — произвольная грамматика.
Построим Э-машину М с входным алфавитом )г и рабочим аЛфавитом )г Ц )й', которая будет сначала переписывать входную цепочку на рабочую ленту, затем производить на рабочей ленте произвольный вывод в Г в обратном порядке, а потом в случае, когда в результате такого «обратного вывода» на рабочей ленте останется только символ 1, уничтожать его и переходить в заключительное состояние; при этом можно сделать так, чтобы ни в каком другом случае заключительное состояние не наступало. Очевидно, Ь(М) = 1.(Г). Подведем итог. В силу только что доказанной теоремы класс языков, порождаемых грамматиками, совпадает с классом языков, допускаемых Э-машинами. Этот последний ввиду теорем 1.2 и 1.3 совпадает с классом множеств значений функций, вычисляемых ДЭ-машинами.
Но легко видеть, что ДЭ-машинами вычисляются в точности те же функции, что и обычными одноленточными машинами Тьюринга (упражнение 1.20), т. е. частично рекурсивные функции *); множества же значений частично рекурсивных функций суть рекурсивно перечислимые множества. Итак, из теорем 1.2 — 1.4 вытекает Теор ем а 1.5. Класс язь!ков, порождагмых грамматиками, совпадает с классом ргкурсивно пергчислимьгх язьсков. Теперь мы можем разъяснить сделанное в $ 1.2 утверждение, что «порождающий» способ описания языков не уступает по силе никакому другому эффективному способу.
Именно, в силу доказанных теорем это утверждение немедленно вытекает из тезиса Черча, согласно которому всякая функция, допускающая вычисление каким-либо эффективным в интуитивном смысле способом, частично рекурсивна. Вместе с тезисом Черча наше утверждение носит, разумеется, не математический, а естественнонаучный характер. Замечание. Из теоремы 1.5 и известной теоремы Поста (см., например, (К1еепе !952], стр. 237 русского перевода), в силу которой множество тогда и только тогда рекурсивно, когда оно само и его дополнение рекурсивно перечислимы, следует — поскольку существуют не- рекурсивные рекурсивно перечислимые множества — замечание, сделанное в конце з 1.2.
') Обычно в курсах теории ялгоритмов с помощью машин Тью. ринга определяются только числовые частично ренурсивные функции, я «словврные» частично рекурсивные функции вводятся с помощью нумерации цепочек. Не составляет большого труда доказать равно. сильность такого определения используемому нами «непосредственному» (точные формулировки см.
в упражнении 1й!). 6! УПРАЖНЕНИЯ ОСНОВНЫЕ ПОНЯТИЯ !ГЛ. 1 Уп раж н е н ив 1.1. Подсчитать число вхождений подцепочек в цепочку длины л. 1.2. Доказать, что для произвольных цепочек ф и ф тогда н только тогда срф = фф, когда существуют цепочка в и числа т, л = О, 1, ... ганне, что ср = в, ф = в". 13. Пусть У = (аь ., а») — некоторый словарь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
