Выполните задание, На бесконечном столе ссть горизонтальная и
вертикальная стены. Правый конец горизонталь-
ной стены соединен с нижним концом вертикаль-
ной стены. Длины стен неизвестны, в каждой
стене есть ровно один проход, точное место про-
хода и его ширина нагзвестны. Робот находится в
клетке, расположенной непосредственно слева от
вертикальной стены у её нижнего конца. На pot-
сунке указан один из возможных распо-
пожження стен и Робота (Робот обозначся буквой
«Р»).
Напишите для Робота алгоритм, закрашивающий псе клетки, распологатенныс непосредственно выше
и горизонтальной стены н левее вертикальной стены. Проходы должны остаться незакрашеннъом. Робот
доласен закрасить только клетки, удовлетворяющие данному условию. Например, для приведенного
выше рисунка Робот должен закрасить следующие клетки (ом, рисунок).
При исполнении алгоритма Робот не должҫн разрушиться, выполненне горитма должно
завершитьса. Конечное расположение Робота может быть произвольным. Алгоритм должен решать зада-
чу для любого допустимого расположения стен и любого расположения и размера проходов внутри стен.
Алгоритм может быть выполнен в среде формального інстиоттеля или записан в текстовом редакторе.
Сохраните алгоритм в текстовог фоайте.​

Меньше чем 3-х основание СС быть не может. (Сама догадайся почему ;-)  

Делим:  

23 : 3 = 7 ост. 2 — подходит  

23 : 4 = 5 ост. 3 — не подходит  

23 : 5 = 4 ост. 3 — не подходит  

23 : 6 = 3 ост. 5 — не подходит  

23 : 7 = 3 ост. 2 — подходит  

23 : 8 = 2 ост. 7 — не подходит  

23 : 9 = 2 ост. 5 — не подходит  

23 : 10 = 2 ост. 3 — не подходит  

23 : 11 = 2 ост. 1 — не подходит  

23 : 12 = 1 ост. 11 — не подходит  

23 : 13 = 1 ост. 10 — не подходит  

23 : 14 = 1 ост. 9 — не подходит  

23 : 15 = 1 ост. 8 — не подходит  

23 : 16 = 1 ост. 7 — не подходит  

23 : 17 = 1 ост. 6 — не подходит  

23 : 18 = 1 ост. 5 — не подходит  

23 : 19 = 1 ост. 4 — не подходит  

23 : 20 = 1 ост. 3 — не подходит  

23 : 21 = 1 ост. 2 — подходит  

23 : 22 = 1 ост. 1 — не подходит  

23 : 23 = 1 ост. 0 — не подходит  

Далее для всех СС больше 23 остаток будет 23. Следовательно нет смысла их рассматривать.  

Итого: 2, 7 и 21.

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 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.