Практическая работа №2 «Разработка программ машин Тьюринга для вычисления функций»
Цель: Формирование умений и навыков по разработке программ машин Тьюринга.
Задачи:
1. изучить устройство машины Тьюринга
2. научиться читать и выполнять программы, написанные для машины Тьюринга
3. научиться разрабатывать программы для машины Тьюринга.
Оснащение урока:
· Техническое: ПК, сканер, принтер, интерактивная доска
· Методическое: инструкционная карта, задание для самостоятельного выполнения
· Программное: Windows XP, тренажер «Машина Тьюринга».
Теоретические сведения: Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга.
Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
1. Внешний алфавит.Конечное множество (обозначают буквой А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ. Например, алфавит машины Тьюринга, работающей с двоичными числами, задается в виде A = {0, 1, а0}. Непрерывную цепочку символов на ленте называют словом.
Автоматом называют устройство, работающее без участия человека. Автомат в машине Тьюринга имеет несколько состояний и при определенных условиях переходит из одного состояния в другое. Множество состояний автомата называют внутренним алфавитом.
3. Внутренний алфавит. Конечное множество состояний каретки (автомата). Обозначается буквой Q={q1,q2...}. Одно из состояний - q1- должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние остановка.
Таблица переходов. Описание поведения автомата (каретки) в зависимости от состояния и считанного символа.
Автомат машины Тьюринга в процессе своей работы управляется программой, во время каждого шага которой выполняются последовательно следующие действия:
· Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
· Передвигаться на одну ячейку влево или вправо.
· Менять свое внутреннее состояние.
Поэтому при составлении программы для каждой пары (символ, состояние) нужно определить три параметра: символ ai из выбранного алфавита A, направление перемещения каретки ("←” — влево, "→” — вправо, "точка” — нет перемещения) и новое состояние автомата qk. Например, команда 1 "←” q2 обозначает "заменить символ на 1, переместить каретку влево на одну ячейку и перейти в состояние q2”.
Ход работы
1. В рабочей тетрадке запишите тему, цель и задачи работы.
2. Приступите к выполнению упражнений.
3. Выполните задание.
4. Сделайте вывод по работе.
Упражнение 1 На ленте записано число в двоичной системе счисления. Каретка находится где-то над числом. Требуется увеличить число на единицу.
Чтобы решить задачу, нам нужно:
· определить алфавит машины Тьюринга А,
· определить набор состояний Q,
· составить программу (т.е. для каждой пары (аi,qi) определить команду автомата.)
·
Алфавит машины Тьюринга, работающей с двоичными цифрами будет включать цифры 0, 1 и пробел a0. Т.е. А={1,0,a0}.
Определим возможные состояния:
1. q1 - автомат ищет правый конец слова (числа) на ленте
2. q2 - автомат увеличивает число на 1, проходя его слева направо и останавливается, закончив работу.
Напишем программу:
1 часть. q1 - автомат ищет правый конец слова (числа на ленте)
1)если в рабочей ячейке записано 0 - переместиться вправо
2)если в рабочей ячейке записано 1 - переместиться вправо
3) если в рабочей ячейке пробел, переместить каретку влево и перейти в состояние q2
Составим таблицу переходов для q1 т.о.:
| q1 | |
| 0 → q1 | |
| 1 → q1 | |
| a0 | a0 ← q2 |
2 часть. q2 - автомат увеличивает число на 1, проходя его слева направо и останавливается, закончив работу.
1) если в рабочей ячейке записана цифра 0, записать в нее 1 и стоп
2) если в рабочей ячейке записана цифра 1, выполнить перенос в старший разряд - записать в ячейку 0 и переместиться влево.
3) если в рабочей ячейке пробел, записать в нее 1 и стоп.
Добавим в нашу таблицу состояние q2:
| алф\состояния | q1 | q2 |
| 0 → q1 | 1 . q0 | |
| 1 → q1 | 0 ← | |
| a0 | a0 ← q2 | 1 . q0 |
Построенная таблица и есть программа для машины Тьюринга.
Упражнение 2 . Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова.
Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая.
Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).
Задания для самостоятельного выполнения
1. Построить таблицу машины Тьюринга, которая заменяет все единицы на нули, а все нули на единицы. Пример. Исходное число 111001. Результат – 000110.
2. Построить таблицу машины Тьюринга, которая удаляет из числа все нули, например, число 1001110 преобразует к виду 1111. Эта задача уже сложнее и требует ввести в рассмотрение более двух состояний.
3. Построить машину, имеющую два конечных состояния, условно обозначаемых как YES и NO. Машина должна завершить работу в состоянии YES, если число единиц в записи числа нечетное, и в состоянии NO– в противном случае.
4. Построить машину, имеющую два конечных состояния, условно обозначаемых как YES и NO. Машина должна завершить работу в состоянии YES, если в записи числа имеется три подряд идущих единицы, и в состоянии NO– в противном случае.
5. Построить машину Тьюринга, которая получает обратный порядок записи числа, например, исходное число 111001, результат 100111.
6. Построить машину Тьюринга, которая меняет местами соседние два элемента попарно. Пример. Исходное число 011001 заменяется на 100110.