Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Если ситуация S' может быть получена из ситуации
5 применением некоторой инструкции, будем говорить,
что S' непосредственно достижима из S (в
машине М), и писать S)=S' или S)=S'. Последовали
тельность ситуаций С = (S0, St, ..., Sn) (п ^ 1) будем называть вычислением (машины М), если St-_! )= Sf для каждого i, 1 ^ i ^ п. Число п называется
ся длиной вычисления С. Если существует вычисление машины М, начинающееся ситуацией S и оканчивающееся ситуацией S', мы говорим, что S' достижима из S (в машине М), и пишем 5>-S' или S>-S'.
м
Вычисление, начинающееся начальной х-ситуацией,
44
ОСНОВНЫЕ понятия
[ГЛ. I
назовем ^-вычислением, вычисление, начинающееся начальной (х-)ситуацией и оканчивающееся заключительной (х-) ситуацией,— полным (х-)вычисле-нием (машины М). х-вычисление, оканчивающееся ситуацией (qf, #х, ф , А, #?/), где qf <= Q0, будем называть [х, ^-вычислением (машины М). (Таким образом, полное х-вычисление— это то же самое, что [х, А]-вычисление.) Если существует полное х-вычис-ление машины М, мы будем говорить, что М допускает цепочку х. Множество цепочек, допускаемых машиной М, мы будем называть языком, допускаемым машиной М, и обозначать L(М).
Заметим, что в процессе х-вычисления граничный маркер, записанный в крайней слева рабочей ячейке, никогда не уничтожается, и ни в какой другой рабочей ячейке он появиться не может. Поэтому мы будем, например, говоря «на рабочей ленте записан только символ Л», «рабочая лента уничтожается» и т. п., подразумевать: «на рабочей ленте записана цепочка #Л», «уничтожаются все ячейки рабочей ленты, кроме той, в которой записан символ ф». Полное вычисление начинается и кончается при отсутствии рабочей ленты; входная цепочка к концу полного вычисления должна быть вся прочитана.
Если каждой инструкции Э-машины М взаимно однозначно сопоставлен некоторый символ Cj, то цепочка с/1 ... с1п, где с/.— символ, сопоставленный инструкции, выполняемой на t-м шаге вычисления С = (50, ... ..., Sn), будет называться шифром вычисления С. Вычисление имеет точно один шифр и вполне определяется этим шифром и исходной ситуацией (ср. упражнения 1.10 и 1.11).
Будем называть Э-машину М детерминированной (ДЭ-м а ш и н о й), если ее программа удовлетворяет следующим двум условиям: (а) она не содержит двух различных инструкций с одинаковыми левыми частями; (б) если некоторое состояние содержится в левой части инструкции одного из типов (i) — (v), то оно не может содержаться в левой части инструкции другого типа.
ДЭ-машина для всякой входной цепочки х имеет не более одного полного х-вычисления.
МАШИНЫ ТЬЮРИНГА
45
Мы будем говорить, что ДЭ-машина, допускающая язык L, распознает этот язык, если для любой цепочки х во входном алфавите она имеет лишь конечное множество х-вычислений (попросту говоря, если, начав работать с произвольной цепочкой на входной ленте, машина в конце концов останавливается). Распознающая язык ДЭ-машина существует тогда и только тогда, когда этот язык рекурсивен (см. ниже, замечание к упражнению 1.22,6)).
Пусть М — Э-машина с входным алфавитом V и рабочим алфавитом W. Назовем Э-машину Л5 с рабочим алфавитом W sV [JW {J{d} (d<?V IJW) прямой одноленточной моделью (п. о. м.) машины М, если [х, г/]-вычисление машины М существует тогда и только тогда, когда в машине Й из ситуации (qi, А, #Ф, А, Ф xd) достижима ситуация вида (<?/, А, #ф, #х> dy), где qf <= Qo.
Лемма 1.5. Для любой Э-машины люжно построить ее п. о, м. Если при этом исходная машина детерминированная, то и п. о. м. можно сделать детерминированной.
Доказательство. Принцип работы Й может быть таким: во «входной зоне» (левее d) и «рабочей зоне» (правее d) рабочей ленты М функционирует точно так же, как М на входной и рабочей лентах соответственно, но всякий раз, когда М переходит от «входного» шага к «рабочему» или наоборот, рабочая головка машины Л5 будет передвигаться из зоны в зону, предварительно поставив в обозревавшейся перед тем ячейке метку, чтобы найти эту ячейку по возвращении. Ясно, что свойство детерминированности, если машина М им обладает, при таком преобразовании сохраняется.
Теорема 1.2. Для любой Э-машины М можно построить ЛЭ-машину Mi такую, что L{Mi) =L(M).
Доказательство. Пусть Р = {си ..., с„} — множество символов, находящееся во взаимно однозначном соответствии с программой машины М. Построим ДЭ-машину Mi с входным алфавитом V и рабочим алфавитом, содержащим V U W U Р U {d,e,f}, где V, W — соответственно входной и рабочий алфавиты машины М и d, е, / ф V U W U Р, работающую следующим образом. Начиная работать в начальной х-ситуации, Mi прежде
46
ОСНОВНЫЕ понятия
[ГЛ. I
всего переписывает х на рабочую ленту, приписывает справа dfcte, передвигает рабочую головку на граничный маркер и переходит в некоторое специальное состояние q'. Дальнейшая работа Mi состоит в последовательном выполнении «макрошагов», которые могут быть описаны следующим образом. Перед началом «макрошага» машина находится в ситуации (q\ фх, ф, Л, ^xdfZe), где Z— некоторая цепочка в алфавите Р. При выполнении «макрошага» Mi функционирует на участке ленты между ф и началом Z, как описанная в доказательстве леммы 1.5 п. о. м. машины М, однако стой разницей, что она производит при этом не любые «М-шаги», а такие, в результате которых получается «.М-вычисле-ние» с шифром Z. Для этого головка перед каждым «.М-шагом» передвигается вправо до символа cj, стоящего непосредственно вслед за f, «перетаскивает» / вправо через этот символ, затем возвращается в ячейку, где следует выполнять очередной «М-шаг» (эта ячейка, разумеется, должна быть ранее помечена), и выполняет его, следуя той инструкции, которая отвечает символу Cj, если эта инструкция применима. Если же она неприменима, то f «перетаскивается» влево, пока не окажется перед первым символом цепочки Z; эта последняя заменяется цепочкой, непосредственно следующей за ней в смысле некоторого, раз навсегда фиксированного стандартного порядка на Р*\ участок ленты между d и f («рабочая зона») уничтожается; метка, имеющаяся на одном из символов цепочки х, стирается; рабочая головка становится на граничный маркер, и машина переходит в состояние q\ после чего выполняется следующий «макрошаг». Если машине удалось «протащить» символ f через всю цепочку Z (так что он оказался непосредственно перед е), то различаются два случая, а) Если имитированное на данном «макрошаге» х-вычисление машины М с шифром Z является полным, то рабочая лента уничтожается и машина останавливается, перейдя в состояние, сигнализирующее об успешном окончании работы, — цепочка х допущена, б) В противном случае дальнейшие действия таковы же, как в рассмотренном выше случае столкновения с неприменимой инструкцией,
