Машина Тьюрига

Эмулятор машины Тьюринга

Другой эмулятор машины Тьюринга

Лекция по машине Тьюринга

Лекция 2 по машине Тьюринга

Практическая работа № 2

"Машина Тьюринга"
Требования к содержанию отчета:

Отчет должен состоять из следующих пунктов:

• заголовок работы (название и цель работы).
• задание к работе.
• постановка задачи Вашего варианта и решение задачи в табличной форме
• описание в словесной  форме того, что выполняется машиной в каждом состоянии.
Ответы на вопросы
1. Что такое управляющая головка машины Тьюринга?
2. Для чего нужна машина Тьюринга?

Пример выполненной работы

На ленте машины Тьюринга находится десятичное число. Определить, делится ли это число на 5 без остатка. Если делится, то записать справа от числа слово “да”, иначе — “нет”. Автомат обозревает некую цифру входного числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

567

Состояние q1 поиск правого конца числа;

состояние q2 анализ младшей цифры числа; если она равна “0” или “5”, т.е. число делится на 5, то переход в состояние q3, иначе переход в состояние q5;

состояние q3 запись буквы “Д” справа от слова на ленте;

состояние q4 запись буквы “А” справа от слова и останов машины;

состояние q5 запись буквы “Н” справа от слова;

состояние q6 запись буквы “Е” справа от слова;

состояние q7 запись буквы “Т” справа от слова и останов машины.


Вариант 1

На ленте машины Тьюринга содержится последовательность символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q1 обозревает один из символов указанной последовательности.

Вариант 2

Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 3

Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q1 обозревает правую цифру числа.

Вариант 4

Дано целое число в троичной системе счисления. Нужно увеличить его на единицу.

Вариант 4 (усложненное)

Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд “( )”.

Например, дано “) ( ( ) ( ( )”, надо получить “) . . . ( ( ”.

Автомат в состоянии q1 обозревает крайний левый символ строки.

Вариант 5

На ленте Машины Тьюринга находится десятичное число. Определить, делится ли оно на 10. Если делится, то рядом написать слово "yes".  Если нет ,то то написать слово "no". Автомат обозревает некую цифру входного числа.

Вариант 6

На ленте машины Тьюринга содержится последовательность символов  *. Напишите программу для машины Тьюринга, которая каждый второй символ  * заменит на  @. Замена начинается с правого конца последовательности. Автомат в состоянии q1 обозревает один из символов указанной последовательности.