Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Второе отличие наших машин от обычных состоит в том, что мы снабдим их двумя лентами, причем одна из
§ 1.4]
МАШИНЫ ТЬЮРИНГА
41
них будет служить «входной»; на этой ленте записывается исходная цепочка, которую машина в процессе работы прочитывает, не изменяя ее, — и, более того, каждый символ читается только один раз; вся остальная работа производится на другой, «рабочей» ленте. Это видоизменение, в отличие от предыдущего, не имеет принципиального значения, но оно позволит нам сделать некоторые рассмотрения более прозрачными*).
Далее, обычно в определение машины Тьюринга включают требование, чтобы из любой ситуации, в которой состояние машины не заключительное, она переходила в некоторую новую ситуацию (в частном случае эта новая ситуация может совпадать со старой); мы же отказываемся от этого требования. Данная модификация также не принципиальна и служит лишь для большего удобства моделирования грамматик.
Последней особенностью наших машин будет «эла* стичность» рабочей ленты. Это означает, что: а) стирая символ в ячейке рабочей ленты, машина (или, если угодно, головка) уничтожает и самое ячейку, так что соседние с ней ячейки становятся соседними между собой («стягивание» ленты); б) между любыми двумя ячейками рабочей ленты машина может создать новую, сразу записав в ней что-либо («растягивание» ленты). При таком способе работы отпадает надобность в «пустом символе». Для нас «эластичность» будет удобна тем, что позволит при моделировании грамматик машинами обходиться без сдвигов всего содержимого ленты, которые иначе пришлось бы производить на каждом шаге.
Перейдем к формулировке определения.
Машина Тьюринга с эластичной рабочей лентой, сокращенно Э-машина, состоит из:
а) двух конечных**) разделенных на ячейки лент — входной и рабочей;
*) Главное преимущество введения входной ленты состоит в том, что МП-машины (см. ниже, § 4.5) становятся частным случаем машин Тьюринга.
**) Имеется в виду конечность ленты в каждый момент работы машины. В процессе работы размеры рабочей ленты могут неограниченно расти; входная лента не меняется в процессе работы, но может оказаться сколь угодно длинной при большом объеме исходных данных.
42
ОСНОВНЫЕ понятия
[ГЛ. I
б) двух алфавитов (словарей) V и W, также называемых входным и рабочим (их элементы называются соответственно входными и рабочими символами);
в) символов ф, ф $zV\JW, называемых соответственно левым и правым граничными маркерами (множества V U {ф, ф} и W U {ф} будут обозначаться соответственно V' и IF');
г) входной и рабочей головок, движущихся по соответствующим лентам (в любой момент работы машины каждая головка обозревает некоторую ячейку своей ленты, иначе — находится в этой ячейке);
д) конечного множества Q = {q1, qs} (внутренних) состояний, в котором выделены элемент qi, называемый начальным состоянием, и непустое подмножество Qo, элементы которого называются заключительными состояниями;
е) п рог рам мы — конечного множества цепочек
в алфавите V' U W U Q U {Л, П, ->}, называемых инструкциями, каждая из . которых имеет один из следующих видов: (i) (ii) Aqa->qp; (iii) qa-*Aq^
(iv) qa-+q$ Л; (v) П. Здесь йеГ, A<=W,qa, <7pe=Q.
Содержательно каждая инструкция интерпретируется как разрешение выполнить некоторые действия, зависящие qt состояния, в котором находится машина, и (вообще Говоря) от обозреваемых головками символов, а также от положения рабочей головки. Именно, инструкция, имеющая в левой части qa и в правой <7р, означает, что, находясь в состоянии qa, машина может в случае (i) при а Ф ф сдвинуть входную головку, если в о б озрев аемой е ю ячейке записан символ
а, на одну ячейку вправо; в случае (ii) уничтожить обозреваемую рабочую ячейку, если в ней записан символ Л, и поместить рабочую головку в ячейку, примыкающую к уничтоженной слева; в случае (iii) создать непосредственно справа от обозреваемой рабочей ячейки новую ячейку, записать там символ А и переместить туда (рабочую) головку; в случаях (iv) и (v) передвинуть рабочую головку, если она не находится в крайней слева, соответственно в крайней справа ячейке, на одну, ячейку влево, соответственно вправо; одновременно машина должна —
МАШИНЫ ТЬЮРИНГА
43
в любом из описанных случаев — перейти в состояние q$ (которое может и совпадать с qa). Особым образом интерпретируется выполнение инструкции типа (i) при а = ф: в этом случае происходит только перемена состояния, а входная головка остается на месте (как и рабочая).
Указанную совокупность действий мы будем называть элементарным шагом (или просто шагом) работы машины.
Вполне возможно, что в некоторый момент дкажутся применимыми несколько разных инструкций, так что машина сможет выполнять любую из них «по выбору»; это и есть недетерминированность.
Полный набор сведений о том, в каком состоянии находится Э-машина, что записано на лентах и какие ячейки обозреваются головками, мы будем называть ситуацией данной машины. Формально ситуацию можно определить как упорядоченную систему (qa,x', х", X', X"), где qa е= Q, /еГ, x"eV'+, ГеГ, X" е W'+. Здесь х'х" — цепочка, записанная на входной ленте, х’ — часть этой цепочки влево от головки, Х'Х" и X' — то же для рабочей ленты. Ситуацию вида (qx, Л, 4МФ, А, #), где х е V*, мы будем называть начальной; ситуацию вида (qf, # х, ф, Л, #), где 9/eQo и ^еУ*, — заключительной; будем употреблять также выражения «начальная лг-ситуа-ц и я», «заключительная х-с и т у а ц и я», смысл которых очевиден.
