December 14, 2017 Лабораторная работа Построить машину Тьюринга

Лабораторная работа.

Необходимо построить машину Тьюринга.

Необходимо сделать программу для машины Тьюринга в виду таблицы, написать словесное описание,  сделать пошаговый  прогон для несколько примеров.

Пример выполнения задания. Необходимо построить машину Тьюринга, которая увеличивает десятичное число на единицу.

Ход выполнения задания. Рассмотрим десятичное число, находящееся на ленте машины Тьюринга. Чтобы увеличить его на единицу необходимо увеличить на единицу его последнюю цифру, если число заканчивается цифрой в диапазоне от 0 до 8, или заменить последнюю цифру 0, а предпоследнюю увеличить на единицу. Пустую ячейку стоить просто заменить единицей. Чтобы построить машину Тьюрингу введем алфавит, который будет состоять из пустого символа  символа и цифр в диапазоне от 0 до 9. Этого алфавита будет достаточно для решения задачи. Далее введем состояния машины Тьюринга. q1- начальное состояние, из которого начинает свою работу машина Тьюринга.  q2 - это состояние, в котором будут осуществляться замены. q0 - пассивное состояние, в котором машина Тьюринга останавливается.

В исходном состоянии q1 ищется правый конец числа.
Когда управляющая головка машины Тьюринга оказывается в пустой ячейке, то она сдвигается влево и переходит в состояние q2. В состоянии q2 осуществляется замена цифры. Если головка встречает символ 0,1 ... 8, то осуществляется замена соответственно на  цифры 1,2,3, ...., 9 и переход в пассивное состояние qo. Если на ленте нет  числа, то пустая ячейка заменяется на 1. Если цифра 9, то она заменяется на 0, головка остается в состоянии q2, сдвигается влево и делает замену согласно командам состояния q2. Головка переходит в пассивное состояние, когда осуществит замену числа, не равного девяти. Таким образом, чтобы построить машину Тьюринга, нужно реализовать следующую программу.

a0 0 1 2 3 4 5 6 7 8 9
q1 a0Лq2 0Пq1 1Пq1 2Пq1 3Пq1 4Пq1 5Пq1 6Пq1 7Пq1 8Пq1 9Пq1
q2 1Нq0 1Нq0 2Нq0 3Нq0 4Нq0 5Нq0 6Нq0 7Нq0 8Нq0 9Нq0 0Лq2

В первом вертикальном столбце представлены состояния машины Тьюрига. Обратите внимание, что состояние q0 не отображается в таблице. В первой горизонтали представлен алфавит. Пустая ячейка обозначается символом a0. На пересечении получаются команды машины Тьюринга. Например, команда 4Пq1 означает, что на ленте надо оставить цифру 4 без изменения в текущей ячейке и сдвинуться на ячейку вправо. Команда a0Лq2 означает, что при достижении головки машины Тьюрига пустой ячейки, ее нужно сдвинуть на одну ячейку влево. Таким образом, приведенная программа позволяет построить машину Тьюрига для решения исходной задачи. Если на ленте задать число 201, то оно в результате работы машины Тьюрига будет заменено на 202, то есть цифра 21 заменится на 2. Команда, которая будет осуществлять замену - 2Нq0. Если на ленте будет находиться число 89, то вначале девятка заменится на 0 командой 0Лq2, а потом 8 будет заменена на 9 командой 9Нq0.

Задания по вариантам на построение машины Тьюринга

Вариант 1. Увеличить на 1 число в четверичной системе счисления (0,1,2,3)

Вариант 2. 1. Увеличить на 1 число в троичной системе счисления (0,1,2)

Вариант 3. . Увеличить на 1 число в семеричной  системе счисления (0,1,2,3,4,6,6)

Вариант 4.

Увеличить на 1 число в восьмеричной системе счисления (0,1,2,3,4,5,6,7)

Вариант 5.

Увеличить на 1 число в пятеричная системе счисления (0,1,2,3,4)

Вариант 6.

1. Увеличить на 1 число в шестеричной  системе счисления (0,1,2,3,4,5)

Дать ответы на контрольные вопросы.

1. Какие состояния использовались в решении задачи?
2. Какие особенности машины Тьюринга?
3. Какие действия выполняет управляющая головка?