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

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

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

Задание №1

В начальном состоянии q0 автомат просматривает заданное число и, попадая на пустую ячейку, делает шаг влево, затем переходит в состояние q1 в ячейку, которая соответствует последней цифре числа. В состоянии q1 происходит увеличение числа на 1 (если младшая цифра числа меньше 7, то после увеличения программа завершается; если младшая цифра равна 7, то вместо неё пишем нуль, смещаемся влево и в пустой клетке пишем 1, либо увеличиваем число перед нулём на 1, например, 1777 →2000, после чего программа завершена).

0 1 2 3 4 5 6 7 a0

q1 1 Н q0 2 Н q0 3 Н q0 4 Н q0 5 Н q0 6 Н q0 7 Н q0 0 Л q1 1 Н q0

Задание №2

В начальном состоянии q0 автомат просматривает заданное число и, попадая на пустую ячейку, делает шаг влево, затем переходит в состояние q1 в ячейку, которая соответствует последней цифре числа. В состоянии q1 происходит уменьшение числа на 1 (если младшая цифра не равна нулю, то после уменьшения программа завершается; если младшая цифра равна нулю, то вместо неё пишем 9, смещаемся влево и снова выполняем вычитание, после чего программа завершена).

0 1 2 3 4 5 6 7 8 9 a0

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

Задание №3

В начальном состоянии q0 автомат просматривает заданное число и, попадая на пустую ячейку, делает шаг влево, затем переходит в состояние q1.

В состоянии q1 уменьшаем младшую цифру на 1 (если уменьшаемая цифра больше 1, то после уменьшения программа завершена; если уменьшаемая цифра равна 0, то вместо неё ставим 9, смещаемся влево и снова выполняем вычитание; если младшая цифра равна 1, то вместо неё пишем 0 и переходим в состояние q2).

В состоянии q2 автомат анализирует является ли нуль старшей цифрой числа. Если нуль не является старшей цифрой числа, то программа завершена. Если нуль является