Решение задач «Решить 5 задач на Машину Тьюринга»,
Теоретические основы информатики,информатика в Новосибирске

1. Дано число n в десятичной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 4. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии. 2. На информационной ленте машины Тьюринга содержится непрерывная последовательность символов «*». Сконструируйте машину Тьюринга для замены каждого шестого символа на символ «!» (отсчет символов начинается с левого края строки). В начальный момент времени автомат обозревает произвольный символ заданной строки. В конечный момент времени он должен обозревать крайний левый символ. Составить программу-таблицу и нарисовать диаграмму переходов. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии. 3. На информационной ленте машины Тьюринга записано число N (N>2) в унарной системе счисления. Читающая головка находится напротив крайнего левого символа в записи числа. Выполните трассировку программы для N=6. Отметьте запрещенные клетки таблицы. Определите, какую задачу она решает. Придумайте, как можно решить эту же задачу, используя меньшее число состояний. Запишите свое решение в виде программы-таблицы. (таблица в 1 файле) 4. Дано число X (X>13)в шестнадцатеричной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения шестнадцатеричного числа на 256, вторая – задачу вычитания 13 из заданного шестнадцатеричного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 256X – 13 и Y2 = (X – 13)*256. 5. (2 файл)