Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Тренажёр «Машина Тьюринга» – это учебная модель универсального исполнителя (абстрактной вычислительной машины), предложенного в 1936 году А. Тьюрингом для уточнения понятия алгоритма. Согласно тезису Тьюринга, любой алгоритм может быть записан в виде программы для машины Тьюринга. Доказано, что машина Тьюринга по своим возможностям эквивалентна машине Поста и нормальным «алгорифмам» Маркова.
Рис. 14. Модель машины Тьюринга
Машина Тьюринга состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может содержать символ из некоторого алфавита A={a0,a1,…,aN}. Любой алфавит содержит символ «пробел», который обозначается как a0 или Λ. При вводе команд пробел заменяется знаком подчеркивания «_».
Машина Тьюринга – это автомат, который управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита A, а столбцы – состояниям автомата Q={q0,q1,…,qM}. В начале работы машина Тьюринга находится в состоянии q1. Состояние q0 – это конечное состояние: попав в него, автомат заканчивает работу.
В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей:
1. символ из алфавита A;
2. направление перемещения: > (вправо), < (влево) или ● (на месте);
3. новое состояние автомата
В верхней части программы находится поле редактора, в которое можно ввести условие задачи в свободной форме.
Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее. Двойным щелчком по ячейке ленты (или щелчком правой кнопкой мыши) можно изменить ее содержимое.
С помощью меню Лента можно запомнить состояние ленты во внутреннем буфере и восстановить ленту из буфера.
В поле Алфавит задаются символы выбранного алфавита. Пробел добавляется к введенным символам автоматически.
В таблице в нижней части окна набирается программа. В первом столбце записаны символы алфавита, он заполняется автоматически. В первой строке перечисляются все возможные состояния. Добавить и удалить столбцы таблицы (состояния) можно с помощью кнопок, расположенных над таблицей.
При вводе команды в ячейку таблицы сначала нужно ввести новый символ, затем направление перехода и номер состояния. Если символ пропущен, по умолчанию он не изменяется. Если пропущен номер состояния, по умолчанию состояние автомата не изменяется.
Справа в поле Комментарий можно вводить в произвольной форме комментарии к решению. Чаще всего там объясняют, что означает каждое состояние машины Тьюринга.
Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость.
Задачи для машины Тьюринга можно сохранять в файлах. Сохраняется условие задачи, алфавит, программа, комментарии и начальное состояние ленты. При загрузке задачи из файла и сохранении в файле состояние ленты автоматически записывается в буфер.
Содержание работы
Запустить программу-эмулятор машины Тьюринга. Ознакомиться с работой эмулятора и набором команд. Воспроизвести (не сохраняя в файл) предложенные выше примеры. По указанию преподавателя выбрать варианты из папки \..Example программы-эмулятора, а, также вариант из Приложения Ж. По завершении работы результаты сохранить в файл.
Дата публикования: 2014-10-20; Прочитано: 957 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!