Задача 10. При решении этой задачи следует обратить внимание на правильное выписывание алфавита: A = {a0, 0, 1

При решении этой задачи следует обратить внимание на правильное выписывание алфавита: A = {a0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, Д, А, Н, Е, Т}.

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

состояние q ₂—анализ младшей цифры числа; если она равна “0” или “5”, т.е. число делится на 5, то переход в состояние q ₃, иначе переход в состояние q ₅;

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

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

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

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

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

Задания по вариантам. По словесному описанию машины Тьюринга построить ее программу (в алфавите {0, 1}).

1) Начав работу с первой единицы массива из единиц, машина “сдвигает” его на две ячейки вправо, не изменяя остального содержимого ленты, и останавливается на последней единице перенесенного массива.

2) Начав двигаться влево от произвольной ячейки, головка находит первую при таком перемещении ячейку с единицей (если такая встретится на пути) и, сделав один шаг вправо, останавливается на соседней ячейке. Содержимое ленты не меняется.

3) Машина начинает работу с самой левой непустой ячейки и отыскивает нуль, примыкающий с левой стороны к первому справа массиву из трех единиц, окаймленному нулями. Головка останавливается на первой единице найденного массива (если такой есть). Содержимое ленты не меняется.

4) Головка машины, начав работу с произвольной ячейки, содержащей единицу, двигается влево до тех пор, пока не пройдет подряд пять нулей. Головка останавливается на первой ячейке слева за этими пятью нулями, напечатав в ней единицу. Остальное содержимое ленты не меняется.

5) При заданном головка машины, начав работу с произвольной ячейки и двигаясь вправо, записывает подряд нулей и останавливается на последнем из них.

6) Головка машины, двигаясь вправо от какой-либо пустой ячейки, находит первый при таком перемещении массив, содержащий не менее семи единиц, стирает в нем первые семь единиц и останавливается на самой правой из ячеек, в которых были стерты единицы. Остальное содержимое ленты не меняется.

7) При заданном значении n головка машины из n записанных единиц оставляет на ленте единицы, так же записанных подряд, если , и работает вечно, если или .

8) Машина реализует алгоритм вычисления функции , считая, что число n представляется записанными подряд n единицами, и массив из n единиц уже найден.

9) Машина реализует алгоритм вычисления функции , считая, что число n представляется записанными подряд n единицами, и массив из n единиц уже найден.

Вопросы для самопроверки

1. Опишите устройство и систему программирования машины Тьюринга.

2. Что такое состояние машины Тьюринга? Сопоставьте устройство машины Тьюринга с устройством компьютера. Какие устройства машины Тьюринга выполняют те же функции, что и аналогичные устройства компьютера?

3. В чем особенность состояний q0 и q1 машины Тьюринга? По какому принципу можно построить программу для машины Тьюринга, которая последовательно выполняет операции А и Б?