Лабораторная «Машина Тьюринга»,
Информатика и КТ в Нижнем Новгороде

6.​ Дано число n в восьмеричной системе счисления. Разработайте машину Тьюринга, которая уменьшала бы заданное число на 3. В начальный и конечном состояниях автомат обозревает крайнюю левую цифру числа. Описать словами каждое состояние автомата. Составить программу-таблицу и нарисовать диаграмму переходов. Отметьте запрещенные клетки таблицы (столбцы таблицы - это состояния q1,q2, .. ,qn). 11.​ На информационной ленте машины Тьюринга содержится два числа в унарной системе счисления, разделенных ровно одним пробелом. Сравнить эти два числа и в пустой клетке между числами поставить один из знаков отношения «<», «>», «=». В начальный момент времени автомат обозревает крайний левый символ первого из чисел. В конечный момент времени он должен обозревать символ операции сравнения. Составить программу-таблицу и нарисовать диаграмму переходов. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии. 20.​ На информационной ленте машины Тьюринга записано натуральное число N в унарной системе счисления. Читающая головка находится напротив крайнего левого символа в записи числа. Выполните трассировку программы для некоторого числа. Определите, какую задачу она решает. Придумайте, как можно решить эту же задачу, используя меньшее число состояний. Запишите свое решение в виде программы-таблицы.(таблица к этой задаче - в прикрепленных файлах)