Приложение Ж

Задачи для самостоятельного решения по теме «Машина Тьюринга»

1. На информационной ленте машины Тьюринга содержится массив символов +. Необходимо разработать функциональную схему машины Тьюринга, которая каждый второй символ + заменит на —. Каретка в начальном состоянии находится где- то над указанным массивом.

2. Дано число п в восьмеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число п на 1.

3. Дана десятичная запись натурального числа п > 1. Разработайте машину Тьюринга, которая уменьшала бы заданное число и на 1. При этом запись числа п – 1 не должна содержать левый нуль, например, 100 – 1 = 99, а не 099. Начальное положение головки – правое.

4. Дан массив из открывающихся и закрывающихся скобок. Постройте машину Тьюринга, которая удаляла бы пары взаимных скобок. Например, дано: «)(()(()», надо получить: «)...((.».

5. Дана строка из букв а и Ь. Разработайте машину Тьюринга, которая переместит все буквы а в левую, а буквы b в правую часть строки. Каретка находится над крайним левым символом строки.

6. Даны два целых положительных числа в десятичной системе счисления. Сконструируйте машину Тьюринга, которая будет находить разность этих чисел, если известно, что первое число больше второго, а между ними стоит знак «минус». Каретка находится над левой крайней цифрой левого числа.

7. Даны два целых положительных числа в различных системах счисления; одно – в троичной системе, другое – в десятичной. Разработайте машину Тьюринга, которая будет находить сумму этих чисел в десятичной системе счисления.

8. Сконструируйте машину Тьюринга, которая выступит в качестве двоично-восьмеричного дешифратора. Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропусков. Необходимо разработать машину Тьюринга, которая будет записывать в десятичной системе счисления число этих меток.

9. На информационной ленте машины Тьюринга в трех секциях в произвольном порядке записаны три различные буквы: А, В и С. Каретка в начальном состоянии обозревает букву, расположенную справа. Необходимо составить функциональную схему машины Тьюринга, которая сумеет поменять местами крайние буквы.

10. Даны два натуральных числа /лил, представленных в унарной системе счисления. Соответствующие наборы символов «|» разделены «–», вслед за последним символом набора л стоит знак «=». Разработайте машину Тьюринга, которая будет находить разность чисел тип. При этом результат должен быть записан следующим образом: если т > л, то справа от «=» должны стоять знак «+» и набор символов «|» в количестве т – п\ если т – л, то справа от знака «=» должна стоять пустая клетка; если т <л, то справа от «=» должны стоять знак «—» и набор символов «|» в количестве л – т.

11. Даны два натуральных числа л и т, заданных в унарной системе счисления. Числа ли/л представлены наборами символов «|», разделенных «\». В конце набора стоит «=». Разработайте машину Тьюринга, которая будет производить деление нацело двух натуральных чисел л и т и находить остаток от деления. При этом результат должен быть записан следующим образом: после «=» должен находиться набор символов «|» частного (он может быть и пустым), после чего ставится знак «(», за которым следует набор символов «|» остатка от деления л на т.

12. На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножьте это число на 2, если каретка находится над крайней левой цифрой числа.

13. На ленте машины Тьюринга находится целое положительное число, записанное в десятичной системе счисления. Найдите произведение этого числа на число 11. Каретка обозревает крайнюю правую цифру числа.

14. На ленте машины Тьюринга находится слово, состоящее из букв латинского алфавита {а, Ь, с, d). Подсчитайте число букв «а» в данном слове и полученное значение запишите на ленту левее исходного слова через пробел. Каретка обозревает крайнюю левую букву.

15. На ленте машины Тьюринга находится десятичное число. Определите, делится ли это число на 5 без остатка. Если делится, то запишите справа от числа слово «да», если нет – «нет». Каретка находится где-то над числом.

16. На ленте машины Тьюринга записано число в десятичной системе счисления. Каретка находится над крайней правой цифрой. Запишите цифры этого числа в обратном порядке.

17. На информационной ленте машины Тьюринга находится десятичное число. Найдите результат целочисленного деления этого числа на 2.

18. На информационной ленте машины Тьюринга находится массив, состоящий только из символов А и В. Сожмите массив, удалив из него все элементы В.

19. На ленте машины Тьюринга находится массив 2 N меток. Уменьшите этот массив в 2 раза.

20. Даны два натуральных числа пит, представленные в унарной системе счисления. Между этими числами стоит знак «?». Выясните отношение тип, т.е. знак «?* замените на один из подходящих знаков «>», «<», «=».

21. Найдите произведение двух натуральных чисел тип, заданных в унарной системе счисления. Соответствующие наборы символов «|» разделены знаком «*», а справа от последнего символа правого члена стоит знак «=». Поместите результат умножения этих чисел вслед за знаком «=».

22. На информационной ленте машины Тьюринга в трех секциях в произвольном порядке записаны три цифры: 1, 2, 3. Каретка обозревает крайнюю левую цифру. Необходимо составить функциональную схему машины Тьюринга, которая расположит эти цифры в порядке возрастания.

23. На ленте машины Тьюринга находится десятичное число. Определите, делится ли это число на 5 без остатка. Если делится, то запишите справа от числа слово «да», если нет – «нет». Каретка находится где-то над числом.

24. На ленте машины Тьюринга записано число в десятичной системе счисления. Каретка находится над крайней правой цифрой. Запишите цифры этого числа в обратном порядке.

25. На информационной ленте машины Тьюринга находится десятичное число. Найдите результат целочисленного деления этого числа на 2.

26. На информационной ленте машины Тьюринга находится массив, состоящий только из символов А и В. Сожмите массив, удалив из него все элементы В.