Практическая работа №21
Тема: «Конструирование машин Тьюринга »
Цель: научится строить машины Тьюринга на специальном тренажере для изучения универсального исполнителя.
Эмулятор машины Тьюринга
Что такое машина Тьюринга?
Машина Тьюринга - это универсальный исполнитель (абстрактная вычислительная машина), предложенный английским математиком А. Тьюрингом в 1936 году как уточнения понятия алгоритма. Согласно тезису Тьюринга, любой алгоритм может быть записан в виде программы для машины Тьюринга.
Машина Тьюринга состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может содержать символ из некоторого алфавита A = {a0,a1,…,aN}. Любой алфавит содержит символ «пробел», который обозначается как a0 или L.
Машина Тьюринга - это автомат, который управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита A, а столбцы - состояниям автомата Q = {q0,q1,…,qM}. В начале работы машина Тьюринга находится в состоянии q1. Состояние q0 - это конечное состояние, попав в него, автомат заканчивает работу.
В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «> » (вправо), «< » (влево) или «.» (на месте)
· новое состояние автомата
При вводе команд пробел заменяется знаком подчеркивания «_ ».
Как работать с программой?
В верхней части программы находится поле редактора, в которое можно ввести условие задачи в свободной форме.
Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее. Двойным щелчком по ячейке ленты (или щелчком правой кнопкой мыши) можно изменить ее содержимое.
С помощью меню Лента можно запомнить состояние ленты во внутреннем буфере и восстановить ленту из буфера.
В поле Алфавит задаются символы выбранного алфавита. Пробел добавляется к введенным символам автоматически.
В таблице в нижней части окна набирается программа. В первом столбце записаны символы алфавита, он заполняется автоматически. В первой строке перечисляются все возможные состояния. Добавить и удалить столбцы таблицы (состояния) можно с помощью кнопок, расположенных над таблицей.
При вводе команды в ячейку таблицы сначала нужно ввести новый символ, затем направление перехода и номер состояния. Если символ пропущен, по умолчанию он не изменяется. Если пропущен номер состояния, по умолчанию состояние автомата не изменяется.
Справа в поле Комментарий можно вводить в произвольной форме комментарии к решению. Чаще всего там объясняют, что означает каждое состояние машины Тьюринга.
Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость.
Задачи для машины Тьюринга можно сохранять в файлах. Сохраняется условие задачи, алфавит, программа, комментарии и начальное состояние ленты. При загрузке задачи из файла и сохранении в файле состояние ленты автоматически записывается в буфер.
Пример 1. Написать машину Тьюринга, которая исправляет ошибку в слове «малако».
Ø Запускаем программу turing.exe.
Ø Вносим символы «аклмо» в алфавит программы.
Ø На ленте начиная с позиции «0» вводим слово «малако».
Ø Удаляем ненужные столбцы Q кнопкой 
.
Ø Заполняем таблицу командами.
о>1
к>1
л>1
м>1
о>1
.0
Ø Запускаем программу.
Задание 1. По ссылке https://kpolyakov.spb.ru/loadstat.php?f=/download/turing.rar скачать и установить программу.
Задание 2.
| 1)Написать машину Тьюринга, которая исправляет ошибку в слове «пороллилагромм». | 2)Написать машину Тьюринга, которая исправляет ошибку в слове «иксковотар». |
Задание 3. Оформите отчет, записав в него таблицы (программы) для машин Тьюринга из задания 2. Опишите как Вы делали задание.