dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 75
Текст из файла (страница 75)
M должна двигаться вправо, оставаясь в состоянии q1, что приводит кМО XXY0q1B. Однако у M в состоянии q1 по символу B перехода нет, поэтому она останавливается, не допуская.8.2.4. Äèàãðàììû ïåðåõîäîâ äëÿ ìàøèí ÒüþðèíãàПереходы машин Тьюринга можно представить графически, как и переходы МПавтоматов. Диаграмма переходов состоит из множества узлов, соответствующих состояниям МТ.
Дуга из состояния q в состояние p отмечена одним или несколькими элементамивида X / Y D, где X и Y — ленточные символы, а D — направление (L или R). Таким образом,если δ(q, X) = (p, Y, D), то отметка X / Y D находится на дуге из q в p. Направление на диаграммах представляется не буквами L и R, а стрелками ← и →, соответственно.Как и в других видах диаграмм переходов, начальное состояние представлено словом“начало” и стрелкой, входящей в это состояние. Допускающие состояния выделены двойными кружками. Таким образом, непосредственно из диаграммы о МТ известно все, кроме того,какой символ обозначает пробел.
В дальнейшем считается, что это B, если не оговорено иное.Пример 8.3. На рис. 8.10 представлена диаграмма переходов для машины Тьюрингаиз примера 8.2. Ее функция переходов изображена на рис. 8.9. 334Стр. 334ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀПример 8.4. Сегодня машины Тьюринга рассматриваются чаще всего в качестве“распознавателей языков” или, что равносильно, “решателей проблем”. Однако самТьюринг рассматривал свою машину как вычислитель натуральнозначных функций. Вего схеме натуральные числа представлялись в единичной системе счисления, как блоки из одного и того же символа, и машина вычисляла, изменяя длину блоков или строяновые блоки где-нибудь на ленте.
В данном простом примере будет показано, как машина Тьюринга может вычислить функцию −& , которая называется монусом (monus)или усеченной разностью (proper subtraction) и определяется соотношением m −& n =max(m – n, 0), т.е. m −& n есть m – n, если m ≥ n, и 0, если m < n.НачалоРис. 8.10. Диаграмма переходов МТ, допускающая цепочки вида 0n1nМТ, выполняющая эту операцию, определяется в видеM = ({q0, q1, …, q6}, {0, 1}, {0, 1, B}, δ, q0, B).Отметим, что, поскольку МТ не используется для допускания входа, множество допускающих состояний не рассматривается.
M начинает с ленты, состоящей из 0m10n и пробелов вокруг, и заканчивает лентой с m −& n символами 0, окруженными пробелами.M циклически находит крайний слева из оставшихся 0 и заменяет его пробелом. Затем движется вправо до 1. Найдя 1, M продолжает движение вправо до появления 0, который меняется на 1. Затем M возвращается влево в поисках крайнего слева 0, которыйидентифицируется после того, как M выходит на пробел и сдвигается вправо на однуклетку.
Повторения заканчиваются в одной из следующих ситуаций.1.В поисках 0 справа M встречает пробел. Это значит, что все n нулей в 0n измененына 1, и n + 1 нулей в 0m заменены пробелами. Тогда M изменяет n + 1 единицу на8.2. ÌÀØÈÍÀ ÒÜÞÐÈÍÃÀСтр. 335335пробелы и добавляет 0, оставляя m – n нулей на ленте. Поскольку в этом случаеm ≥ n, то m – n = m −& n.2.Начиная цикл, M не может найти 0, чтобы заменить его пробелом, поскольку первыеm нулей уже изменены на B. Это значит, что n ≥ m, и m −& n = 0.
M заменяет все оставшиеся символы 1 и 0 пробелами и заканчивает работу с пустой лентой.На рис. 8.11 представлены правила функции переходов δ, а на рис. 8.12 — ее диаграмма. Роль каждого из семи ее состояний описывается следующим образом.Символ1Bq0(q1, B, R) (q5, B, R)—q1(q1, 0, R)(q2, 1, R)—q2(q3, 1, L)(q2, 1, R) (q4, B, L)q3(q3, 0, L)(q3, 1, L) (q0, B, R)q4(q4, 0, L)(q4, B, L) (q6, 0, R)q5(q5, B, R) (q5, B, R) (q6, B, R)Состояниеq60———Рис. 8.11. Машина Тьюринга, вычисляющая функцию усеченной разностиНачалоРис. 8.12.
Диаграмма переходов для МТ из примера 8.4336Стр. 336ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀq0 — данное состояние начинает цикл и прерывает его, когда нужно. Если M обозревает0, цикл должен повториться. 0 меняется на B, головка сдвигается вправо, и M переходит в состояние q1. Если же M обозревает 1, то все возможные соответствия между двумя группами нулей на ленте установлены, и M переходит в состояние q5 дляопустошения ленты.q1 — в этом состоянии M пропускает начальный блок из 0 в поисках 1. Найдя ее, M переходит в состояние q2.q2 — M движется вправо, пропуская группу из 1 до появления 0.
0 меняется на 1, головкасдвигается влево, и M переходит в состояние q3. Однако возможно также, что послеблока из единиц символов 0 уже не осталось. Тогда M в состоянии q2 обнаруживаетB. Возникает ситуация 1, описанная выше, где n нулей второго блока использованыдля удаления n из m нулей первого блока, и вычитание почти закончено.
M переходит в состояние q4, предназначенное для преобразования всех 1 в пробелы, а одногопробела — в 0.q3 — M движется влево, пропуская 0 и 1 до появления пробела. Тогда M сдвигаетсявправо и возвращается в состояние q0, начиная новый цикл.q4 — вычитание закончено, но один лишний 0 из первого блока был ошибочно замененпробелом. M движется влево, заменяя все 1 пробелами, до появления B. Последнийменяется на 0, и M переходит в состояние q6, где и останавливается.q5 — это состояние достигается из q0, если обнаруживается, что все 0 из первого блоказаменены пробелами. В случае, описанном выше в 2, усеченная разность равна 0. Mзаменяет все оставшиеся 0 и 1 пробелами и переходит в состояние q6.q6 — единственной целью этого состояния является разрешить M остановиться послевыполнения работы.
Если бы вычисление разности было подпрограммой другой,более сложной функции, то q6 начинало бы следующий шаг этого более объемноговычисления.8.2.5. ßçûê ìàøèíû ÒüþðèíãàСпособ допускания языка машиной Тьюринга уже описан интуитивно. Входная цепочка помещается на ленту, и головка машины начинает работу на крайнем слева символе.
Если МТ в конце концов достигает допускающего состояния, то вход допускается, впротивном случае — нет.Более формально, пусть M = (Q, Σ, Γ, δ, q0, B, F) — машина Тьюринга. Тогда L(M)*представляет собой множество цепочек w из Σ*, для которых q0w |− αpβ при некоторомсостоянии p из F и произвольных ленточных цепочках α и β. Это определение было принято при обсуждении машины Тьюринга в примере 8.2, допускавшей цепочки вида 0n1n.Языки, допустимые с помощью машин Тьюринга, часто называются рекурсивно перечислимыми , или РП-языками. Термин “рекурсивно перечислимые” происходит от вы8.2.
ÌÀØÈÍÀ ÒÜÞÐÈÍÃÀСтр. 337337числительных формализмов, предшествовавших машинам Тьюринга, но определявшихтот же класс языков или арифметических функций. Обсуждение источников этого термина представлено во врезке в разделе 9.2.1.Ñîãëàøåíèÿ ïî îáîçíà÷åíèÿì ìàøèí ÒüþðèíãàОбычно для машин Тьюринга используются такие же символы, как и для других видов автоматов.1. Строчные буквы из начала алфавита обозначают входные символы.2. Прописные буквы, обычно из конца алфавита, используются для ленточных символов, которые иногда могут быть и входными. Однако для пробела всегда используется B.3.
Строчные буквы из конца алфавита обозначают цепочки входных символов.4. Греческие буквы используются для цепочек ленточных символов.5. Буквы p, q и другие около них в алфавите обозначают состояния.8.2.6. Ìàøèíû Òüþðèíãà è îñòàíîâСуществует еще одно понятие “допустимости” для машин Тьюринга — допустимостьпо останову. Говорят, что машина Тьюринга останавливается, если попадает в состояние q, обозревая ленточный символ X, и в этом положении нет переходов, т.е. δ(q, X) неопределено.Пример 8.5. Машина Тьюринга M из примера 8.4 была построена для того, чтобыдопускать язык; она не рассматривалась с точки зрения вычисления функции.
Заметим,однако, что M останавливается на всех цепочках из символов 0 и 1, поскольку независимо от входной цепочки машина M в конце концов удаляет вторую группу нулей6, еслиможет ее найти, достигает состояния q6 и останавливается. Всегда можно предполагать, что МТ останавливается, если допускает. Таким образом, без изменения допускаемого языка можно сделать δ(q, X) неопределенной, если q —допускающее состояние. Итак,• предполагается, что МТ всегда останавливается в допускающем состоянии.К сожалению, не всегда можно потребовать, чтобы МТ останавливалась, если не допускает. Язык машины Тьюринга, которая в конце концов останавливается независимоот того, допускает она или нет, называется рекурсивным, и его важные свойства будутрассматриваться, начиная с раздела 9.2.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
