В троичной машине Поста дан массив ловок из 0 и 1

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

2. Дано число n в восьмеричной системе счисления. Создать машину Тьюринга, которая увеличивала бы данное число n на 1. Автомат в состоянии q1 обозревает некоторую цифру входного слова. Не считая самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

3. Дана десятичная запись натурального числа n gt; 1. Создать машину Тьюринга, которая уменьшала бы данное число n на 1. Автомат в состоянии q1 обозревает правую цифру числа. Не считая самой программки-таблицы, обрисовать словами, что выполняется машиной в каждом состоянии.

4. Дано естественное число n gt; 1. Создать машину Тьюринга, которая убавляла бы заданное число n на 1, при этом в выходном слове старшая цифра не обязана быть 0. Например, если входным словом было 100, то выходным словом должно быть 99, а не 099. Автомат в состоянии q1 обозревает правую цифру числа. Не считая самой программки-таблицы, обрисовать словами, что производится машиной в каждом состоянии.

5. Дан массив из раскрывающих и покрывающих скобок. Выстроить машину Тьюринга, которая удаляла бы пары обоюдных скобок, т.е. расположенных подряд ( ).

Например, дано ) ( ( ) ( ( ), надобно получить ) . . . ( ( .

Автомат в состоянии q1 обозревает последний левый символ строки. Кроме самой программки-таблицы, обрисовать словами, что выполняется машиной в каждом состоянии.

6. Дана строчка из букв a и b. Создать машину Тьюринга, которая переместит все буквы a в левую, а буковкы b в правую доли строчки. Автомат в состоянии q1 обозревает последний левый символ строчки. Не считая самой программки-таблицы, обрисовать словами, что выполняется машиной в каждом состоянии.