В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.
Практические задания:
1. A = { λ, 1, # }. Сложить два числа 11#11111.
2. A = { λ, 1, # }. Найти разницу двух чисел 1111#111.
3. A = { λ, 1, # }. Найти произведение двух чисел 111#111.
4. A = { λ, 1 }. Найти половину заданного четного числа 11111111.
5. A = { λ, a, b, c }. Приписать слева к непустому слову P его первый символ.
6. А = { λ, a, b, c }. Перенести первый символ непустого слова Р в его конец.
7. А = { λ, a, b }. Удалить из слова Р его второй символ, если такой есть.
8. А = { λ, a, b, c }. Удалить из слова Р первое вхождение символа a.
9. А = { λ, a, b, c }. Удалить из P все вхождения символа a.
10. А = { λ, a, b, = }. Удвоить слово P, поставив между ним и его копией знак «=».
11. A = { λ, a, b }. Перевернуть слово P (например: abb → bba).
12. A = { λ, 1 }. Определить, делится ли число, записанное в унарной системе счисления, на 3.
13. A = { λ, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }. Дано число в унарной системе счисления. Преобразовать его к десятичному виду.
14. A = { λ, 1 }. Пусть слово P является записью числа 2n (n=0, 1, 2, …) в унарной системе. Получить в этой же системе число n.
15. А = { λ, a, b }. Если в P символов a больше, чем символов b, то выдать ответ a, если символов a меньше символов b, то выдать ответ b, а иначе в качестве ответа выдать пустое слово.
Astana - 2014
Дата добавления: 2014-12-20; просмотров: 115 | Поможем написать вашу работу | Нарушение авторских прав |