Поделиться
Л3-00132.docx
Машина Тьюринга
1. Наберите программу из учебника (или из презентации), которая увеличивает двоичное число на 1 и проверьте её работу.
Будет ли правильно работать эта программа, если вначале каретка расположена справа от числа? Почему?
Ответ:
2. Измените программу для увеличения двоичного числа на 1 так, чтобы она работала правильно, если вначале каретка расположена справа от числа.
|
|
q1 |
q2 |
|
0 |
® |
1 . q0 |
|
1 |
® |
0 ¬ |
|
¨ |
¬ q2 |
1 . q0 |
3. Опишите алгоритм работы программы для машины Тьюринга:
|
|
q1 |
q2 |
|
а |
q2 |
¨ ¬ |
|
б |
q2 |
¨ ¬ |
|
¨ |
¬ |
q0 |
Ответ:
q1 –
q2 –
При каком начальном состоянии ленты и положении каретки эта программа зацикливается?
Ответ:
Лента:
Каретка:
4. Составьте программу для машины Тьюринга, которая заменяет в двоичном числе все 0 на 1 и все 1 на 0 (из числа 10101100 получается 01010011). Каретка находится слева от числа.
|
|
q1 |
q2 |
|
0 |
|
|
|
1 |
|
|
|
¨ |
|
|
Описание состояний:
q1 –
q2 –
5. Составьте программу для машины Тьюринга, которая умножает двоичное число на 2. Каретка находится над числом.
|
|
q1 |
|
0 |
|
|
1 |
|
|
¨ |
|
Описание состояний:
q1 –
6. Составьте программу для машины Тьюринга, которая увеличивает троичное число на 1. Каретка находится справа от числа.
|
|
q1 |
q2 |
|
0 |
|
|
|
1 |
|
|
|
2 |
|
|
|
¨ |
|
|
Описание состояний:
q1 –
q2 –
При каком начальном положении каретки эта программа зацикливается?
Ответ:
7. Составьте программу для машины Тьюринга, которая уменьшает двоичное число на 1. Каретка находится над числом.
|
|
q1 |
q2 |
q3 |
q4 |
|
0 |
|
|
|
|
|
1 |
|
|
|
|
|
¨ |
|
|
|
|
Описание состояний:
q1 –
q2 –
q3 –
q4 –
При каком начальном положении каретки эта программа зацикливается?
Ответ:
8. Составьте программу для машины Тьюринга, которая умножает троичное число на 2. Каретка находится над числом.
|
|
q1 |
q2 |
q3 |
|
0 |
|
|
|
|
1 |
|
|
|
|
2 |
|
|
|
|
¨ |
|
|
|
Описание состояний:
q1 –
q2 –
q3 –
9. Дана строка, состоящая только из символов «а» и «б». Составьте программу для машины Тьюринга, которая переставляет последний символ в начало строки. Каретка находится над первым символом строки.
|
|
q1 |
q2 |
q3 |
q4 |
|
а |
|
|
|
|
|
б |
|
|
|
|
|
¨ |
|
|
|
|
Описание состояний:
q1 –
q2 –
q3 –
q4 –
10. *Дана строка, состоящая только из символов «а» и «б». Составьте программу для машины Тьюринга, которая сортирует символы, то есть переставляет все буквы «а» в начало строки. Каретка находится над первым символом строки. Используйте состояния, которые перечислены род таблицей.
|
|
q1 |
q2 |
q3 |
q4 |
|
а |
|
|
|
|
|
б |
|
|
|
|
|
¨ |
|
|
|
|
Описание состояний:
q1 – каретка идёт вправо по цепочке букв «а»
q2 – каретка идёт вправо по цепочке букв «б»
q3 – каретка идёт влево и ищет конец цепочки букв «б»
q4 – замена буквы «б» на букву «а»
11. *Составьте программу для машины Тьюринга, которая складывает два числа в двоичной системе, разделенные на ленте знаком «+».
12. *Составьте программы для машины Тьюринга, которые увеличивают и уменьшают на единицу число, записанное в десятичной системе счисления.
13. Составьте программы для машины Тьюринга, которые выполняют сложение и вычитание двух чисел в десятичной системе счисления.
Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
