Конструирование МТ

Архив содержит файлы решенных задач на МТ следующих вариантов:
Вариант 2
Дано число п в восьмеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число n на 1.
Вариант 3
Дана десятичная запись натурального числа п
1. Разработайте машину Тьюринга, которая уменьшала бы заданное число n на
1. При этом запись числа п - 1 не должна содержать левый нуль, например,
100-1 = 99, а не
099. Начальное положение головки - правое.
Вариант 5
Дана строка из букв а и b. Разработайте машину Тьюринга, которая переместит все буквы а в левую, а буквы b в правую часть строки. Каретка находится над крайним левым символом строки.
Вариант 8
Сконструируйте машину Тьюринга, которая выступит в качестве двоично-восьмеричного дешифратора.
Вариант 10
На информационной ленте машины Тьюринга в трех секциях в произвольном порядке записаны три различные буквы: А, B и С. Каретка в начальном состоянии обозревает букву, расположенную справа. Необходимо составить функциональную схему машины Тьюринга, которая сумеет поменять местами крайние буквы.
Вариант 11
Даны два натуральных числа m и n представленных в унарной системе счисления. Соответствующие наборы символов « | » разделены « - », вслед за последним символом набора п стоит знак «=». Разработайте машину Тьюринга, которая будет находить разность чисел т и п. При этом результат должен быть записан следующим образом: если т п, то справа от «=» должны стоять знак «+» и набор символов « | » в количестве т- п; если т = п, то справа от знака «=» должна стоять пустая клетка; если т п, то справа от «=» должны стоять знак « - » и набор символов « | » в количестве п - т.
Вариант 12
Даны два натуральных числа п и т, заданных в унарной системе счисления. Числа п и т представлены наборами символов « | », разделенных « \ ». В конце набора стоит «=». Разработайте машину Тьюринга, которая будет производить деление нацело двух натуральных чисел п и т и находить остаток от деления. При этом результат должен быть записан следующим образом: после «=» должен находиться набор символов « | » частного (он может быть и пустым), после чего ставится знак «(», за которым следует набор символов « | » остатка от деления п на т.
Вариант 13
На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножьте это число на 2, если каретка находится над крайней левой цифрой числа.
Вариант 15
На ленте машины Тьюринга находится слово, состоящее из букв латинского алфавита {а, b, с, d}. Подсчитайте число букв «а» в данном слове и полученное значение запишите на ленту левее исходного слова через пробел. Каретка обозревает крайнюю левую букву.
Вариант 16
На ленте машины Тьюринга находится десятичное число. Определите, делится ли это число на 5 без остатка. Если делится, то запишите справа от числа слово «да», если нет — «нет». Каретка находится где-то над числом.
Вариант 17
На ленте машины Тьюринга записано число в десятичной системе счисления. Каретка находится над крайней правой цифрой. Запишите цифры этого числа в обратном порядке.
Вариант 19
На информационной ленте машины Тьюринга находится массив, состоящий только из символов А и B. Сожмите массив, удалив из него все элементы B.
Вариант 20
Число п задано на ленте машины Тьюринга массивом меток. Преобразуйте это значение п по формуле:
Каретка обозревает крайнюю левую метку.
Вариант 21
Число п задано на ленте машины Тьюринга массивом меток. Преобразуйте это значение п по формуле:
Каретка обозревает крайнюю левую метку.
Вариант 22
Налейте машины Тьюринга находится массив 2N меток. Уменьшите этот массив в 2 раза.
Вариант 23
Даны два натуральных числа п и т, представленные в унарной системе счисления. Между этими числами стоит знак «? ». Выясните отношение т и п, т. е. знак «? » замените на один из подходящих знаков « », « », «=».
Вариант 25
На информационной ленте машины Тьюринга в трех секциях в произвольном порядке записаны три цифры: 1, 2,
3. Каретка обозревает крайнюю левую цифру. Необходимо составить функциональную схему машины Тьюринга, которая расположит эти цифры в порядке возрастания.