1. На ленте машины Тьюринга содержится последовательностью символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q1 обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
2. Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
3. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
4. Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
5. Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд “( )”.
Например, дано “) ( ( ) ( ( )”, надо получить “) . . . ( ( ”.
Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
6. Дана строка из букв “a” и “b”. Разработать машину Тьюринга, которая переместит все буквы “a” в левую, а буквы “b” — в правую части строки. Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
70, 35, 43, 132, 121, 11, 60, 64, 24, 31
Объяснение:
1) Изначально s = 0, затем на каждой из 12 – 6 + 1 = 7 итераций к ней прибавляется 10, итого получится 70
2) Аналогично, s = 0 + 7 * (8 – 3) = 35
3) Итерация с i = 1: k = 2 * 4 + 1 = 9. Итерация с i = 2: k = 2 * 9 + 2 = 20. Итерация с i = 3: k = 2 * 20 + 3 = 43.
4) s = 0 + 12 * 11 = 132
5) s = 0 + 11 * (12 – 1) = 121
6) u = 26 – 1 – 2 – 3 – 4 – 5 = 11
7) s = 4 + 5 + … + 11 = 60
8) s = 1 * 2 * 2 * … * 2 (8 – 3 + 1 раз) = 64
9) y = 0 + 4 * 1 + 4 * 2 + 4 * 3 = 24
10) s = 3 + 2 * 2 + 2 * 3 + 2 * 4 + 2 * 5 = 31
1) 3
2) 1 3
3) 1 1 1 3
4) 3 1 1 3
5) 1 3 2 1 1 3
6) 1 1 1 3 1 2 2 1 1 3
7) 3 1 1 3 1 1 2 2 2 1 1 3
8) 1 3 2 1 1 3 2 1 3 2 2 1 1 3
9) 1 1 1 3 1 2 2 1 1 3 1 2 1 1 1 3 2 2 2 1 1 3
10) 3 1 1 3 1 1 2 2 2 1 1 3 1 1 1 2 3 1 1 3 3 2 2 1 1 3
11) 1 3 2 1 1 3 2 1 3 2 2 1 1 3 3 1 1 2 1 3 2 1 2 3 2 2 2 1 1 3
ответ: на одиннадцатом шаге он записал такую последовательность чисел:
1 3 2 1 1 3 2 1 3 2 2 1 1 3 3 1 1 2 1 3 2 1 2 3 2 2 2 1 1 3