Гладкий - Формальные грамматики и языки - 1973, страница 8

Ча. Я„ук-» А„у,М4„у„если либо э ~ и я~муж Чб. Еолуш ку ви. -+ Аху родЗолу ху в.н Чв Зиеолуш ху виа + Аку имЕиеодуш ху вин Ч1. 5!лук — Зукдх ЧПа. Я, „е, ух-и ями(ику,, парень„„ ... 8неодуш ср ук + ПО !гул, Ко" леса„ш ... ЧПб. А„у,-»молодой,„ш сверхскоростнойк„„ ... ЧПв. У„у-+ехал„у, летел„„, ... ЧПг. Ьос! -р по Оулу дае; ЬОС»-» ИЗ Оулу род, ОГ О!хе род', 1 ОСЗ Р В Еуху внш На 3!хе виш ш4хд дае 1.0с4 + мимО шоку рода вдоль 5!хе рол' 1.ос — р пешком, верхом, Н43 ~!ну предла В ~!ну предл (Здесь ямщик„, и т.

и. — сокращенная запись; например, я нщинрод. мн. означает ямщиков.) млшины тьюринга основные понятия [гл. г а ! .4! 4О Концепция машины Тьюринга, которой мы будем пользоваться, отличается от обычной, излагаемой в руководствах по теории алгоритмов (см., например, [К1еепе 1952)). Поскольку наше изложение рассчитано на читателя, знакомого с основами теории алгоритмов, мы не будем в основном тексте касаться вопроса о взаимоотношении нашей концепции с обычной и отнесем это в упражнения.

По той же причине мы,не разбираем примеров и проводим рассуждения о машинах Тьюринга по большей части «на пальцах», на уровне объяснения руководящих идей (но достаточно подробно, чтобы знакомый с соответствушщей техникой читатель мог восстановить все формальные детали; тем, кто найдет свой уровень владения этой техникой,недостаточным, полезно выполнить упражнения !.16 †!.19). Само определение машины также не будет до конца формализованным; в нем будут фигурировать такие наглядные образы, как «лента», «ячейка, обозреваемая головкой» и т. п.; впрочем, в этом мы следуем традиции. Обычная «классическая» машина Тьюринга представляет собой устройство для реализации алгоритмов. Работа алгоритма есть детерминированный процесс каждый следующий его шаг жестко определяется предыдущим, и ход всего процесса полностью предопределен исходными данными.

Для достижения такой детерминированности на машину Тьюринга в ее классическом виде накладывается требование ни в какой момент не допускать возможности выполнения двух разных команд. Нам, однако, понадобятся и такие машины Тьюринга, которые реализуют не алгоритмы, а исчисления, сходные с грамматиками, — «недетерминированные машины Тьюринга»; формально они будут отличаться от обычных только отсутствием упомянутого только что требования. Впрочем, термин «недетерминированная машина Тьюринга» неудобен: детерминированная машина оказывается частным случаем недетерминированной. Поэтому мы будем называть недетерминированные в указанном только что смысле машины просто «машинами Тьюринга», а «классические» вЂ” «детерминированными машинами Тьюринга».

Второе отличие наших машин от обычных состоит в том, что мы снабдим их двумя лентами, причем одна из нн х будет служить «входной»; на этой ленте записышина в п оцессе вается исходная цепочка, которую ма Р яя ее, — и, более того, ра боты прочитывает, не изменяя ее,— ждый символ читается только од р ин аз; вся остальная ка а гой, «рабочей» ленте. то работа производится на друг ", видоизменение, в , в отличие от предыдущего, не им позволит нам сделать инципиального значения, но оно позволит при некоторые рассмотрения более р р Д . обычно в определение машины ьюринг чают т ебование, чтобы из любой си у ц та ии вкоашины не заключительное, она пере- торой состояние машины не за л ходила в некоторую нову у ю сит ацию в част т а ия может совпадать со ста Последней особенностью наших машин удет « ы.

Это означает, что: а1 стирая стичность» рабочей ленты. то в ячейке рабочей ленты, машина хили, е» ленты); б) между любыми д умя ячей- («стягиванне» ленты ; ет создать новую, сраабочей ленты машина може («растягивание» ленты). При б падает надобность в «пусто писав в ней что-ли о и таком способе ра оты от ичность» будет удобна тем, символ». е», Для нас «эластичн пии грамматик машина- что позволи р т п и моделировании содержимого ленты, ми обходи иться без сдвигов всего соде бы производить на каждом которые иначе пришлось ы шаге. Перейдем к формулировке опр д е еления.

Тью инга с эластичной ра чей лентой, сокращенно -маши з*) азделенных на ячейки лент— а) двух конечных ) равд входной и рабочей; п еим щесгво введения входной ленты состоит в том, что - „е й 4.Б) становятся частным случаем ма- чго МП-машины (см„ниже, й . стано л нгы в каждый мом нт работы **) Имеетсн в виду конечность ленты б й . енгы могут неограни- машины. В процессе работы р р азме ы ра оче л ченно расти; входна я лента не меняется в процесс большом объеме исходных жег оказаться сколь угод О д н линней при данных, 42 основнын понятия б) двух алфавитов (словарей) У и 1(У, также называемых входным и рабочим (их элементы называются соответственно входными и рабочими символами); в) символов ЧР, ф Зм(ГЦ(2', называемых соответственно левым и правым граничными марк е р а м и (множества К Ц Щ, ф) и Р Ц Щ) будут обозначаться соответственно 1" и 1«"); г) входной и рабочей головок, движущихся по соответствующим лентам (в любой момент работы машины каждая головка о б о з р е в а е т некоторую ячейку своей ленты, иначе — находится в этой ячейке); д) конечного множества Я = (дь ..., д,) (внутр е н н и х) с о с т о я н и й, в котором выделены элемент аь называемый начальным состоянием, и непустое подмножество Ям элементы которого называются заключительными состояниями; е) п р ог р а м м ы — конечного множества цепочек в алфавите К'ЦК Ц ЯЦ(Л, П, — »), называемых инструкциями, каждая из которых имеет один из следующих видов, '(1) д«а-»д„; (11) Аа«-+а«; (ш) а„-»Аа,; (1ч) а„-+дЭЛ; (ч) д„— «даП.

Здесь аеи)", А~В', а„а «на, Содержательно каждая инструкция интерпретируется как разрешение выполнить некоторые действия, зависящие цт состояния, в котором находится машина, и (вообще 1оворя) от обозреваемых головками символов, а также от положения рабочей головки. Именно, инструкция, имеющая в левой части д„и в правой аа,означает, что, находясь в состоянии д„, машина может в случае (Ц при а чь ф сдвинуть входную головку, е ел и в обозреваемой ею ячейке записан символ а, на одну ячейку вправо; в случае (й) уничтожить обозреваемую рабочую ячейку, если в ней з аписа н с н м в о л А, и поместить рабочую головку в ячейк, примыкающую к уничтоженной слева; в случае (ш) соу адать непосредственно с п р а в а от обозреваемой рабочей ячейки новую ячейку, записать там символ А и переместить туда (рабочую) головку; в случаях (1ч) и (ч) передвинуть рабочую головку, е с л и о н а н е н а х одится в крайней слева, соответственно в крайней сп р а в а я че йке, на одну ячейку влево, соответственно вправо; одновременно машина должна— МАШИНЫ ТЬЮРИНГА 4 1А1 43 в любом из описанных случаев — перейти в состояние дз (которое может и совпадать с а„).

Особым образом интерпретируется выполнение инструкции типа (1) при а = ф: в этом случае происходит только перемена состояния, а входная головка остается на месте (как и рабочая). Указанную совокупность действий мы будем называть элементарным шагом (нлн просто шагом) работы машины. Вполне возможно, что в некоторый момент окажутся применимыми несколько разных инструкций, так что машина сможет выполнять любую из них «по выбору»; это и есть недетерминированность.

Полный набор сведений о том, в каком состоянии находится Э-машина, чтб записано на лентах и какие ячейки обозреваются головками, мы будем называть с и т у а ц и е й данной машины. Формально ситуацию можно определить как упорядоченную систему (а„,х', х", Х', Х"), где 2„ ~ Я, х' е= $"', х" ~ Р«+, Х' еи В"', Х" еи 1(7". Здесь х'х" — цепочка, записанная на входной ленте, х' — часть этой цепочки влево от головки, Х'Х" и Х' — то же для рабочей ленты.

Ситуацию вида (дь Л, ~хф, Л, ~ф), где х еи У', мы будем называть начальной; ситуацию вида (ау, ~х, ч, Л, $=), где дг ен Я» и хе:— У', — за ключ и тельной; будем употреблять также выражения «на ч а льна я х-си ту ац и я», «з а к л ю ч и т е л ь н а я х-с и т у а ц и я», смысл которых очевиден. Если ситуация 5' может быть получена из ситуации 5 применением некоторой инструкции, будем говорить, что 5' непосредственно достижим а из 5 (в машине М), и писать 5)=5' или 5~=5'. Последовательность ситуаций С = (5ь 5Ь ..., 5„) (и > 1) будем называть вычислением (машины М), если 5,,»=5, для каждого 1, 1 (1( а.

Число и называется дл и н о й вычисления С. Если существует вычисление машины М, начинающееся ситуацией 5 и оканчивающееся ситуацией 5', мы говорим, что 5' д остижима из 5 (в машине М), и пишем 5Р-5' или 5Р-5'. м Вычисление, начинающееся начальной х-ситуацией, 45 няшины тьюгингх 4 1л! основныв понятия 44 !ГЛ. 1 назовем х-в ы ч н с л е н и е м, вычисление, начинающееся начальной (х-) ситуацией и оканчивающееся заключительной (х-) ситуацией, — п о л и ы м (х-) в ы ч и с л ен нем (машнны М).

х-вычнсление, оканчиваюшееся ситуацией (дь ~х, ф, Л, ~у), где д1 ен 4',1о, будем называть [х, у]-вычислением (машины М). (Таким образом, полное х-вычисление — это то же самое, что [х, Л]-вычисление.) Если сушествует полное х-вычисление машины М, мы будем говорить, что М дои у с к а е т цепочку х.

Множество цепочек, допускаемых машиной М, мы будем называть я з ы к о м, до п у с к а ем ы м м а ш и н о й М, н обозначать Е (М). Заметим, что в процессе х-вычислення граничный маркер, записанный в крайней слева рабочей ячейке, никогда не уничтожается, и ни в какой другой рабочей ячейке он появиться не может. Поэтому мы будем, например, говоря «на рабочей ленте записан только символ А», «рабочая лента уничтожается» и т. п., подразумевать: «на рабочей ленте записана цепочка чрА», «уничтожаются все ячейки рабочей ленты, кроме той, в которой записан символ ~». Полное вычисление начинается и кончается при отсутствии рабочей ленты; входная цепочка к концу полного вычисления должна быть вся прочитана.

Если каждой инструкции Э-машины М взаимно однозначно сопоставлен некоторый символ сь то цепочка сй ... сью гДе сб — символ, сопоставленный инстРУкции, выполняемой на 1см шаге вычисления С = (5, ..., 3 ), будет называться ш и ф р о м вычисления С. Вычисление имеет точно один шифр и вполне определяется этим шифром и исходной ситуацией (ср.