Машина Тьюринга

Порождение цепочек символов можно рассматривать как результат работы некоторого гипотетического устройства. Рассмотрим работу гипотетического устройства называемого машинойТьюринга (рис.9.3).

Рис. 9.3

Вдоль бесконечной ленты, разделенной на клетки, перемещается управляющая головка (УГ). Заданы внешний алфавит М = { m ₁, m ₂,..., m_n }, внутренний алфавит S = { S ₀, S ₁,..., S_r }, и алфавит перемещений D = { П, Л, Н }. Все клетки ленты заполнены символами из M.

Управляющая головка может находиться в тех или иных состояниях, характеризуемых символами из S. Состояние S ₀ особое. Если УГ находится в состоянии S ₀, то машина не производит никакой работы (выключена). Предполагается, что в конце работы машина всегда переходит в состояние S ₀. В процессе работы машины УГ может перемешаться в дискретные такты времени вдоль ленты. Перемещение происходит либо на одну клетку вправо (П), Либо на одну клетку влево (Л). Перемещение УГ в данный такт работы может отсутствовать (Н).

В каждый такт работы УГ совершает следующие действия:

1) считывает символ m_i, находящийся в клетке ленты, которую в этом такте видит УГ;

2) в соответствии со считанным символом m_i, и своим состоя­нием S_j записывает символ m_k в эту клетку;

3) движется (не движется) вдоль ленты;

4) переходит в следующее состояние S_p.

Всю работу машины можно задать с помощью функциональной таблицы Т, в клетках которой стоят тройки вида m_k, S_p, d_i, где d_i Î D — символ, определяющий перемещение. Таким образом, функциональная таблица определяет отображение M ´ S в M ´ S ´ D. Содержательный смысл отображения (m_i, S_j) ® (m_k, S_p, d_i)состоит в том, что, находясь в состоянии S_j и считывая из клетки символ m_i, УГ записывает в данную клетку ленты символ m_k, пе­реходит в состояние S_p и производит движение, определяемое сим­волом d_i. Условимся, что функциональная таблица всегда устрое­на так, что имеет место отображение (m_i, S ₀) ® (m_i, S ₀, H). Это означает, что в выключенном состоянии машина не работает.

До начала функционирования машины (если это необходимо) надо заполнить некоторые клетки ленты символами, отличными от m ₀, перевести УГ в состояние, отличное от S ₀, и задать исход­ное положение УГ относительно ленты. После этого машина будет функционировать в соответствии с таблицей Т. Функционирова­ние машины можно задать с помощью графа, вершины которого взаимно однозначно соответствуют состояниям этого устройства, дуги – переходам из одного состояния в другое, при этом каж­дая дуга (S_i, S_p) взвешена парой (m_i, m_kd_l).

Дата добавления: 2014-12-27