Практическая работа № 36
«Машина Тьюринга»

1. Наберите программу из учебника (или из презентации), которая увеличивает двоичное число на 1 и проверьте её работу.

Будет ли правильно работать эта программа, если вначале каретка расположена справа от числа? Почему?

Ответ:

2. Измените программу для увеличения двоичного числа на 1 так, чтобы она работала правильно, если вначале каретка расположена справа от числа.

3. Опишите алгоритм работы программы для машины Тьюринга:

Ответ:

При каком начальном состоянии ленты и положении каретки эта программа зацикливается?

Ответ:

4. Составьте программу для машины Тьюринга, которая заменяет в двоичном числе все 0 на 1 и все 1 на 0 (из числа 10101100 получается 01010011). Каретка находится слева от числа.

Описание состояний:

5. Составьте программу для машины Тьюринга, которая умножает двоичное число на 2. Каретка находится над числом.

Описание состояний:

6. Составьте программу для машины Тьюринга, которая увеличивает троичное число на 1. Каретка находится справа от числа.

Описание состояний:

При каком начальном положении каретки эта программа зацикливается?

Ответ:

7. Составьте программу для машины Тьюринга, которая уменьшает двоичное число на 1. Каретка находится над числом.

Описание состояний:

При каком начальном положении каретки эта программа зацикливается?

Ответ:

8. Составьте программу для машины Тьюринга, которая умножает троичное число на 2. Каретка находится над числом.

Описание состояний:

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

Описание состояний:

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

Описание состояний:

11. *Составьте программу для машины Тьюринга, которая складывает два числа в двоичной системе, разделенные на ленте знаком «+».

12. *Составьте программы для машины Тьюринга, которые увеличивают и уменьшают на единицу число, записанное в десятичной системе счисления.

13. Составьте программы для машины Тьюринга, которые выполняют сложение и вычитание двух чисел в десятичной системе счисления.