Практическая работа № 37
«Машина Поста»

1. Что делает следующая программа для машины Поста?

Ответ:

Как она будет работать при различных начальных состояниях ленты?

Ответ:

2. Напишите программу для машины Поста, которая неприменима (то есть зацикливается) при любом начальном состоянии ленты.

3. Напишите программу для машины Поста, которая увеличивает на 1 число, записанной в унарной системе счисления. Каретка стоит над первой (самой левой) отметкой.

4. Решите задачу 2 при условии, что в начале работы каретка расположена где-то справа от записи числа.

5. Напишите программу для машины Поста, которая уменьшает на 1 число, записанной в унарной системе счисления. Каретка стоит над первой (самой левой) отметкой.

6. На ленте расставлены метки, между которыми могут быть пропуски длиной в одну ячейку. Заполнить все пропуски метками. Каретка стоит над самой левой меткой.

7. *Напишите программу для машины Поста, которая удваивает число, записанное в единичной системе счисления. Каретка расположена над первой отметкой числа.

8. *Напишите программу для машины Поста, которая складывает два числа в единичной системе счисления. Каретка расположена над пробелом, разделяющим эти числа на ленте.

9. *Напишите программу для машины Поста, которая складывает два числа, записанных в унарной системе. Числа расположены на неизвестном расстоянии друг от друга. Каретка находится над левой границей первого (левого) числа.

10. **Напишите программу для машины Поста, которая складывает несколько натуральных чисел. Каждое число кодируется как последовательность расположенных рядом отметок (в унарной системе счисления). Числа отделены друг от друга пробелами. Каретка находится справа от первого числа.

11. **Написать программу для машины Поста, которая находит единственную метку на ленте, которая расположена неизвестно где. Каретка должна остановиться на метке, все другие (временные) метки должны быть стерты. В начале работы каретка расположена над пустой ячейкой.