Машина Тьюринга
тренажер для изучения универсального исполнителя
Что это такое?
Тренажёр «Машина Тьюринга» — это учебная модель
универсального исполнителя (абстрактной вычислительной машины), предложенного в 1936 году
А. Тьюрингом для
уточнения понятия алгоритма.
Согласно тезису Тьюринга, любой алгоритм может быть записан в виде программы для машины Тьюринга.
Доказано, что машина Тьюринга по своим возможностям эквивалентна
машине Поста и нормальным алгорифмам Маркова.
Машина Тьюринга состоит из каретки (считывающей и записывающей головки) и бесконечной
ленты, разбитой на ячейки. Каждая ячейка ленты может содержать символ из некоторого
алфавита A={a0,a1,…,aN}.
Любой алфавит содержит символ «пробел», который обозначается как
a0 или Λ.
При вводе команд пробел заменяется знаком подчеркивания «_».
Машина Тьюринга — это автомат, который управляется таблицей.
Строки в таблице соответствуют символам выбранного алфавита A, а
столбцы — состояниям автомата Q={q0,q1,…,qM}.
В начале работы машина Тьюринга находится в состоянии q1.
Состояние q0 — это конечное состояние: попав в него, автомат заканчивает работу.
В каждой клетке таблицы, соответствующей некоторому символу
ai и некоторому состоянию qj,
находится команда, состоящая из трех частей:
- символ из алфавита A;
- направление перемещения: > (вправо), < (влево) или . (на месте);
- новое состояние автомата
Новости
10 января 2013 г.
Выпущена версия 1.1. Исправлены мелкие ошибки.
Где почитать ещё?
- Фалина И.Н. Тема «Машина Тьюринга» в школьном курсе информатики
(inf.1september.ru).
- Майер Р.В. Машины Поста и Тьюринга (komp-model.narod.ru).
- Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В.
Машина Тьюринга и алгоритмы Маркова. Решение задач, М.: МГУ, 2006.
- Бекман И.Н. Компьютерные науки. Лекция 7. Алгоритмы (profbeckman.narod.ru)
- Соловьев А. Дискретная математика без формул (lib.rus.ec)
- Ершов С.С. Элементы теории алгоритмов, Челябинск, Издательский центр ЮУрГУ, 2009.
- Варпаховский Ф.Л. Элементы теории алгоритмов, М: Просвещение, 1970.
- Верещагин Н.К., Шень А. Вычислимые функции, М: МЦНМО, 1999.
Что с этим делать?
В верхней части программы находится поле редактора, в которое можно ввести условие задачи в свободной форме.
Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее.
Двойным щелчком по ячейке ленты (или щелчком правой кнопкой мыши) можно изменить ее содержимое.
С помощью меню Лента можно запомнить состояние ленты во внутреннем буфере и
восстановить ленту из буфера.
В поле Алфавит задаются символы выбранного алфавита. Пробел добавляется к
введенным символам автоматически.
В таблице в нижней части окна набирается программа. В первом столбце записаны символы алфавита,
он заполняется автоматически. В первой строке перечисляются все возможные состояния. Добавить
и удалить столбцы таблицы (состояния) можно с помощью кнопок, расположенных над таблицей.
При вводе команды в ячейку таблицы сначала нужно ввести новый символ, затем направление
перехода и номер состояния. Если символ пропущен, по умолчанию он не изменяется. Если
пропущен номер состояния, по умолчанию состояние автомата не изменяется.
Справа в поле Комментарий можно вводить в произвольной форме комментарии к решению.
Чаще всего там объясняют, что означает каждое состояние машины Тьюринга.
Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас
будет выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость.
Задачи для машины Тьюринга можно сохранять в файлах. Сохраняется условие задачи,
алфавит, программа, комментарии и начальное состояние ленты. При загрузке задачи
из файла и сохранении в файле состояние ленты автоматически записывается в буфер.
Если вы заметили ошибку или у вас есть
предложения, замечания, жалобы, просьбы и заявления, пишите.
Технические требования
Программа работает под управлением операционных систем
линейки Windows на любых современных компьютерах.
Лицензия
Программа является бесплатной для некоммерческого использования.
Исходные тексты программы не распространяются.
Программа поставляется «as is», то есть, автор не несет никакой
ответственности за всевозможные последствия ее использования,
включая моральные и материальные потери, вывод оборудования из
строя, физические и душевные травмы.
При размещении программы на других веб-сайтах ссылка на первоисточник обязательна.
Без письменного согласия автора
ЗАПРЕЩАЕТСЯ:
- 1) публикация материалов в любой форме, в том числе размещение материалов на других Web-сайтах;
- 2) распространение неполных или измененных материалов;
- 3) включение материалов в сборники на любых носителях информации;
- 4) получение коммерческой выгоды от продажи или другого использования материалов.
Использование и скачивание материалов означает, что вы приняли условия этого лицензионного соглашения.
Скачать
Пароль к архиву — kpolyakov.spb.ru
В архив включены следующие файлы:
| turing.exe |
основная программа — учебная модель «Машины Тьюринга» |
| EXAMPLES |
подкаталог с примерами программ для тренажера «Машина Тьюринга« |
После распаковки архива программа находится в работоспособном состоянии и
не требует никаких дополнительных установок.
Обучающие видео
Машина Тьюринга
