В.Н. Пильщиков, В.Г. Абрамов, А.А. Вылиток, И.В. Горячая - Машина Тьюринга и алгоритмы Маркова. Решение задач

Московский государственный университет им. М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиВ.Н. Пильщиков, В.Г. Абрамов,А.А. Вылиток, И.В. ГорячаяМашина Тьюринга и алгоритмы Маркова.Решение задач(Учебно-методическое пособие)Москва, 2006УДК 681.325.5ББК 22.18П32Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. МашинаТьюринга и алгоритмы Маркова. Решение задач. (Учебно-методическоепособие) - М.: МГУ, 2006.

– 47 с.Издательский отдел факультета ВМК МГУ (лицензия ЛР №040777 от 23.07.96)Пособие посвящено решению задач по теме «Введение в теорию алгоритмов», изучаемой на первом курсе факультета ВМК МГУ в рамках дисциплины«Алгоритмы и алгоритмические языки». Это задачи на составление алгоритмовв виде машины Тьюринга и нормальных алгоритмов Маркова, а также задачитеоретического характера.В пособии приводятся необходимые сведения по теории алгоритмов,подробно объясняются типичные приёмы решения задач и предлагается большой набор задач для самостоятельного решения.Пособие рассчитано на студентов первого курса факультета ВМК МГУ ипреподавателей, ведущих семинарские занятия по программированию.Рецензенты:доцент Баула В.Г.доцент Корухова Л.С.Печатается по решению Редакционно-издательского совета факультетавычислительной математики и кибернетики МГУ им. М.В.

Ломоносова.ISBN???© Издательский отдел факультетавычислительной математики и кибернетикиМГУ им. М.В. Ломоносова, 200621. Машина ТьюрингаВ разделе рассматриваются задачи на составление алгоритмов длямашины Тьюринга. Приводится краткое описание этой машины, на примерахобъясняются основные приёмы составления таких алгоритмов и предлагаютсязадачи для самостоятельного решения.1.1 Краткое описание машины ТьюрингаСтруктура машины ТьюрингаМашина Тьюринга (МТ) состоит из двух частей – ленты и автомата (см.слева):лента:автомат:ab↑qbΛΛab↑qbΛΛЛента используется для хранения информации. Она бесконечна в обестороны и разбита на клетки, которые никак не нумеруются и не именуются.

Вкаждой клетке может быть записан один символ или ничего не записано.Содержимое клетки может меняться – в неё можно записать другой символ илистереть находящийся там символ.Договоримся пустое содержимое клетки называть символом «пусто» иобозначать знаком Λ («лямбда»). В связи с этим изображение ленты, показанноена рисунке справа, такое же, как и на рисунке слева. Данное соглашение удобнотем, что операцию стирания символа в некоторой клетке можно рассматриватькак запись в эту клетку символа Λ, поэтому вместо длинной фразы «записатьсимвол в клетку или стереть находящийся там символ» можно говорить просто«записать символ в клетку».Автомат – это активная часть МТ.

В каждый момент он размещается пододной из клеток ленты и видит её содержимое; это видимая клетка, анаходящийся в ней символ – видимый символ; содержимое соседних и другихклеток автомат не видит. Кроме того, в каждый момент автомат находится водном из состояний, которые будем обозначать буквой q с номерами: q1, q2 ит.п.

Находясь в некотором состоянии, автомат выполняет какую-тоопределённую операцию (например, перемещается направо по ленте, заменяявсе символы b на a), находясь в другом состоянии – другую операцию.Пару из видимого символа (S) и текущего состояния автомата (q) будемназывать конфигурацией и обозначать <S, q>.Автомат может выполнять три элементарных действия: 1) записывать ввидимую клетку новый символ (менять содержимое других клеток автомат неможет); 2) сдвигаться на одну клетку влево или вправо («перепрыгивать» сразучерез несколько клеток автомат не может); 3) переходить в новое состояние.Ничего другого делать автомат не умеет, поэтому все более сложные операциитак или иначе должны быть сведены к этим трём элементарным действиям.3Такт работы машины ТьюрингаМТ работает тактами, которые выполняются один за другим. На каждомтакте автомат МТ выполняет три следующих действия, причем обязательно вуказанном порядке:1) записывает некоторый символ S′ в видимую клетку (в частности, можетбыть записан тот же символ, что и был в ней, тогда содержимое этой клетки неменяется);2) сдвигается на одну клетку влево (обозначение – L, от left), либо на однуклетку вправо (обозначение – R, от right), либо остается неподвижным (обозначение – N).3) переходит в некоторое состояние q′ (в частности, может остаться в прежнем состоянии).Формально действия одного такта будем записывать в виде тройки:S′, [L,R,N], q′где конструкция с квадратными скобками означает возможность записи в этомместе любой из букв L, R или N.

Например, такт *,L,q8 означает запись символа * в видимую клетку, сдвиг на одну клетку влево и переход в состояние q8.Программа для машины ТьюрингаСама по себе МТ ничего не делает. Для того чтобы заставить её работать,надо написать для неё программу. Эта программа записывается в видеследующей таблицы:S1q1…qj…qmS2…Si…SnΛS΄, [L, R, N], q΄Слева перечисляются все состояния, в которых может находиться автомат,сверху – все символы (в том числе и Λ), которые автомат может видеть наленте. (Какие именно символы и состояния указывать в таблице – определяетавтор программы.) На пересечениях же (в ячейках таблицы) указываются тетакты, которые должен выполнить автомат, когда он находится в соответствующем состоянии и видит на ленте соответствующий символ.В целом таблица определяет действия МТ при всех возможных конфигурациях и тем самым полностью задаёт поведение МТ.

Описать алгоритм ввиде МТ – значит предъявить такую таблицу.(Замечание. Часто МТ определяют как состоящую из ленты, автомата ипрограммы, поэтому при разных программах получаются разные МТ. Мы жебудет считать, в духе современных компьютеров, что МТ одна, но она можетвыполнять разные программы.)4Правила выполнения программыДо выполнения программы нужно проделать следующие предварительныедействия.Во-первых, надо записать на ленту входное слово, к которому будетприменена программа. Входное слово – это конечная последовательностьсимволов, записанных в соседних клетках ленты; внутри входного слова пустыхклеток быть не должно, а слева и справа от него должны быть только пустыеклетки. Пустое входное слово означает, что все клетки ленты пусты.Во-вторых, надо установить автомат в состояние q1 (указанное в таблицепервым) и разместить его под первым символом входного слова:a↑q1bbЕсли входное слово пустое, то автомат может смотреть в любую клетку, т.к. всеони пусты.После этих предварительных действий начинается выполнение программы.

В таблице отыскивается ячейка на пересечении первой строки (т.к. автоматнаходится в состоянии q1) и того столбца, который соответствует первомусимволу входного слова (это необязательно левый столбец таблицы), ивыполняется такт, указанный в этой ячейке. В результате автомат окажется вновой конфигурации. Теперь такие же действия повторяются, но уже для новойконфигурации: в таблице отыскивается ячейка, соответствующая состоянию исимволу этой конфигурации, и выполняется такт из этой ячейки. И так далее.Когда завершается выполнение программы? Введём понятие тактаостанова.

Это такт, который ничего не меняет: автомат записывает в видимуюклетку тот же символ, что и был в ней раньше, не сдвигается и остается впрежнем состоянии, т.е. это такт S,N,q для конфигурации <S, q>. Попав на тактостанова, МТ, по определению, останавливается, завершая свою работу.В целом возможны два исхода работы МТ над входным словом:1) Первый исход – «хороший»: это когда в какой-то момент МТ останавливается(попадает на такт останова).

В таком случае говорят, что МТ применима к заданному входному слову. А то слово, которое к этому моменту получено на ленте,считается выходным словом, т.е. результатом работы МТ, ответом.В момент останова должны быть выполнены следующие обязательныеусловия:– внутри выходного слова не должно быть пустых клеток (отметим, что вовремя выполнения программы внутри обрабатываемого слова пустые клеткимогут быть, но в конце их уже не должно остаться);– автомат обязан остановиться под одним из символов выходного слова (подкаким именно – не играет роли), а если слово пустое – под любой клеткой ленты.52) Второй исход – «плохой»: это когда МТ зацикливается, никогда непопадая на такт останова (например, автомат на каждом шаге сдвигается вправои потому не может остановиться, т.к.

лента бесконечна). В этом случае говорят,что МТ неприменима к заданному входному слову. Ни о каком результате притаком исходе не может идти и речи.Отметим, что один и тот же алгоритм (программа МТ) может бытьприменимым к одним входным словам (т.е. останавливаться) и неприменимымк другим (т.е. зацикливаться). Таким образом, применимость/неприменимостьзависит не только от самого алгоритма, но и от входного слова.На каких входных словах алгоритм должен останавливаться? На, таксказать, хороших словах, т.е.

на тех, которые относятся к допустимымисходным данным решаемой задачи, для которых задача осмысленна. Но наленте могут быть записаны любые входные слова, в том числе и те, для которыхзадача не имеет смысла; на таких словах поведение алгоритма не фиксируется,он может остановиться (при любом результате), а может и зациклиться.Соглашения для сокращения записиДоговоримся о некоторых соглашениях, сокращающих запись программыдля МТ.1) Если в такте не меняется видимый символ, или автомат не сдвигается, илине меняется состояние автомата, то в соответствующей позиции такта мы небудем ничего писать.Например, при конфигурации <a, q1> следующие записи тактов эквивалентны:a,R,q3b,N,q2a,L,q1a,N,q1≡≡≡≡,R,q3b, ,q2,L,, ,(но не Λ,R,q3 !!)(это такт останова)Замечание. Запятые в тактах желательно не опускать, т.к.

иначе возможнапутаница, если среди символов на ленте могут встретиться буквы L и R.2) Если надо указать, что после выполнения некоторого такта МТ должнаостановиться, то в третьей позиции этого такта будем писать знак «!».Например, такт b,L,! означает следующие действия: запись символа b ввидимую клетку ленты, сдвиг влево и останов.Формально можно считать, что в программе МТ имеется состояние сназванием !, во всех ячейках которого записаны такты останова. При этом,однако, такую строку явно не выписывают, а лишь подразумевают.3) Если заранее известно, что в процессе выполнения программы не можетпоявиться некоторая конфигурация, тогда, чтобы подчеркнуть это явно, будем всоответствующей ячейке таблицы рисовать крестик. (Формально этот крестиксчитается тактом останова.)Эти соглашения необязательны, но они сокращают запись программы иупрощают её восприятие.61.2 Примеры на составление программ для МТРассмотрим примеры на составление программ для МТ, чтобы продемонстрировать некоторые типичные приёмы программирования на МТ.Для сокращения формулировки задач введём следующие два соглашения:– буквой Р будем обозначать входное слово;– буквой А будем обозначать алфавит входного слова, т.е.

набор тех символов, из которых и только которых может состоять Р (отметим, однако, что впромежуточных и выходном словах могут появляться и другие символы).Пример 1 (перемещение автомата, замена символов)А={0,1,2,3,4,5,6,7,8,9}. Пусть Р – непустое слово; значит, Р – это последовательность из десятичных цифр, т.е. запись неотрицательного целого числа вдесятичной системе. Требуется получить на ленте запись числа, которое на 1больше числа Р.Решение.Для решения этой задачи предлагается выполнить следующие действия:1.