План лабораторной работы
1. Прочитать раздел Структура машины Тьюринга.
2. Открыть эмулятор[1] машины Тьюринга http://cmcmsu.no-ip.info/1course/alg.schema.mt.htm. Изучить примеры.
3. Инсталлировать эмулятор emt_setup.exe и ознакомиться с его возможностями по Руководству (в файле .pdf). Выполнить ранее изученные примеры (см. п. 2).
4. Изучить и выполнить пример 1 стр. 4.
5. Решать задачи стр.5.
- Необходимость и способы уточнения понятия алгоритма (символы и слова ) [1, стр.27 – 36]
- Машина Тьюринга (структура, такт работы, запись программы, правила выполнения программы, применимость и неприменимость алгоритма к слову, соглашения для сокращения записи программы). Возможности МТ (композиция, разветвление и повторение МТ) Тезис Тьюринга. [2]
- Изучить примеры [2] стр. 7 – 15
- Решить задачи [2] стр. 15 – 18. Тема «Программирование для МТ» войдет в состав контрольной работы.
Литература
1. Кнут Д. Искусство программирования для ЭВМ. Основные алгоритмы: т.1; М.:Мир,2000..
2. Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач. (Учебно-методическое пособие) — М.: МГУ, 2006. – 47 с.
Структура машины Тьюринга
Машина Тьюринга (МТ) состоит из двух частей – ленты и автомата (головки чтения/записи):
Лента используется для хранения информации. Она бесконечна в обе стороны и разбита на клетки, которые никак не нумеруются и не именуются. В каждой клетке может быть записан один символ или ничего не записано. Содержимое клетки может меняться – в неё можно записать другой символ или стереть находящийся там символ.
Договоримся пустое содержимое клетки называть символом «пусто» и обозначать знаком ? («лямбда»). В связи с этим изображение ленты, показанное на рисунке справа, такое же, как и на рисунке слева. Данное соглашение удобно тем, что операцию стирания символа в некоторой клетке можно рассматривать как запись в эту клетку символа ?, поэтому вместо длинной фразы «записать символ в клетку или стереть находящийся там символ» можно говорить просто «записать символ в клетку».
Автомат – это активная часть МТ. В каждый момент он размещается под одной из клеток ленты и видит её содержимое; это видимая клетка, а находящийся в ней символ – видимый символ; содержимое соседних и других клеток автомат не видит. Кроме того, в каждый момент автомат находится в одном из состояний, которые будем обозначать буквой q с номерами: q1, q2 и так далее. Находясь в некотором состоянии, автомат выполняет какую-то определённую операцию (например, перемещается направо по ленте, заменяя все символы b на a), находясь в другом состоянии – другую операцию.
Пару из видимого символа (S) и текущего состояния автомата (q) будем называть конфигурацией, и обозначать .
Автомат может выполнять три элементарных действия:
- записывать в видимую клетку новый символ (менять содержимое других клеток автомат не может);
- сдвигаться на одну клетку влево или вправо («перепрыгивать» сразу через несколько клеток автомат не может);
- переходить в новое состояние.
Ничего другого делать автомат не умеет, поэтому все более сложные операции так или иначе должны быть сведены к этим трём элементарным действиям.
Такт работы машины Тьюринга
МТ работает тактами, которые выполняются один за другим. На каждом такте автомат МТ выполняет три следующих действия, причем обязательно в указанном порядке:
записывает некоторый символ S? в видимую клетку (в частности, может быть записан тот же символ, что и был в ней, тогда содержимое этой клетки не меняется);
сдвигается на одну клетку влево (обозначение – L, от left), либо на одну клетку вправо (обозначение – R, от right), либо остается неподвижным (обозначение – N).
переходит в некоторое состояние q? (в частности, может остаться в прежнем состоянии).
Формально действия одного такта будем записывать в виде тройки: S?, [L,R,N], q?, где конструкция с квадратными скобками означает возможность записи в этом месте любой из букв L, R или N. Например, такт *,L,q8 означает запись символа * в видимую клетку, сдвиг на одну клетку влево и переход в состояние q8.
Программа для машины Тьюринга
Сама по себе МТ ничего не делает. Для того чтобы заставить её работать, надо написать для неё программу. Эта программа записывается в виде следующей таблицы:
Слева перечисляются все состояния, в которых может находиться автомат, сверху – все символы (в том числе и ?), которые автомат может видеть на ленте. (Какие именно символы и состояния указывать в таблице – определяет автор программы.) На пересечениях же (в ячейках таблицы) указываются те такты, которые должен выполнить автомат, когда он находится в соответствующем состоянии и видит на ленте соответствующий символ.
В целом таблица определяет действия МТ при всех возможных конфигурациях и тем самым полностью задаёт поведение МТ. Описать алгоритм в виде МТ – значит предъявить такую таблицу.
Замечание. Часто МТ определяют как состоящую из ленты, автомата и программы, поэтому при разных программах получаются разные МТ. Мы же будет считать, в духе современных компьютеров, что МТ одна, но она может выполнять разные программы.
