Сейчас мы более подробно разберем устройство Машины Тьюринга (МТ). При чтении двух предыдущих постов на эту тему, может показаться, что это “устройство” имеет очень сложную конструкцию. Но на самом деле это не так. Конструкция МТ очень простая.
Основными её компонентами являются лента бесконечная в обоих направлениях (хотя на практике часто используют ленту ограниченную с одного конца) и считывающая головка.
Внутри неё две катушки с лентой. Такая кассета вставлялась в магнитофон, у которого была считывающая головка. Может аналогия и не слишком хорошая, но для понимания терминов “лента” и “головка” я думаю достаточно.
Конструкция МТ выглядит следующим образом:
На ленте располагаются символы из заранее заданного алфавита S = {S0, S1,...,Sn}. Головка может находится в одном из ограниченного количества состояний Q={Q0, Q1, …, Qm}. Головка МТ перемещается по ленте, считывает и записывает символы, расположенные на ней и переходит в одно из m своих состояний. Работу МТ можно описать с помощью следующих функций:
Q(t+1) = G(Q(t), S(t)) - определяет в какое состояние перейдёт МТ в момент t+1 если в момент t состояние было Q(t), а с ленты был считан символ S(t).
R(t+1) = F(Q(t), S(t)) - определяет какой символ из алфавита S МТ запишет на ленту в момет t+1 если в момент t состояние было Q(t), а с ленты был считан символ S(t).
Как вы можете заметить эти функции очень похожи на те с помощью которых мы описывали поведение конечного автомата. (см. http://attempts-to-see.blogspot.ru/2012/10/blog-post_26.html). Но для МТ требуется ещё одна функция, определяющая направление движения головки.
D(t+1)=D(Q(t), S(t)) - определяет влево или вправо подвинется головка МТ в момет t+1 если в момент t состояние было Q(t), а с ленты был считан символ S(t).
Вот в принципе и всё описание. Теперь для большей наглядности приведём пример МТ. Пример взят из книги Марвина Мински “Вычисления и автоматы”
Ниже представлена МТ, которая определяет чётное или нечётное количество единиц в двоичном числе находящемся на ленте.
Для начала зададим алфавит: S = {0, 1, B}, теперь определим необходимое число состояний Q={Q0, Q1, H} и укажем направления движения R - вправо, L - влево.
Алгоритм работы МТ проще записать в следующем виде:
1) Q0 0 -> Q0 0 R
2) Q0 1 -> Q1 0 R
3) Q0 B -> H 0 -
4) Q1 0 -> Q1 0 R
5) Q1 1 -> Q0 0 R
6) Q1 B -> H 1 -
Такая запись читается следующим образом, начнём с первой строчки:
Q0 0 -> Q0 0 R
Если МТ находится в состоянии Q0 и с ленты считан символ 0, то перейти в состояние Q0, на ленту записать символ 0 и подвинуть головку вправо на один символ.
Остальные строчки интерпретируются аналогично.
Теперь записав любое число на ленту в двоичном виде и, завершив его символом B, можно определить чётное или нет количество единиц в нём (числе).
Пусть лента и головка находятся в состояниях приведённых выше.
Первой выполнится команда 1 (Q0 0 -> Q0 0 R). В результате получим:
Далее снова команда 1 (Q0 0 -> Q0 0 R).
Теперь уже команда 2 (Q0 1 -> Q1 0 R).
Команда 5 (Q1 1 -> Q0 0 R).
Команда 1 (Q0 0 -> Q0 0 R).
Команда 2 (Q0 1 -> Q1 0 R).
Команда 6 (Q1 B -> H 1 -).
В результате МТ остановилась, записав на место символа B символ 1, что означает, что количество единиц нечётное.
Продолжение следует.
Комментариев нет:
Отправить комментарий