Математическая теория формальных языков

       

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


Определение 14.1.1.

Машиной Тьюринга называется семерка

где Q, и - конечные множества, , , ,

и

Здесь Q - множество состояний - входной алфавит (внешний алфавит), - ленточный алфавит (tape alphabet), b0 - бланк (пробел, пустой символ, blank symbol), - множество переходов, I - множество начальных состояний, F - множество заключительных состояний.

Определение 14.1.2.

Конфигурацией машины Тьюринга называется любая четверка , где , , , .

Определение 14.1.3.

Определим на множестве всех конфигураций машины Тьюринга M бинарное отношение

(такт работы) следующим образом.

Если , то

для всех

и .

Если , то

для всех ,

и .

Если , то

для всех ,

и .

Замечание 14.1.4.

Если из контекста ясно, о какой машине Тьюринга идет речь, вместо

будем писать просто .

Определение 14.1.5.



Как и для МП-автомата, для машины Тьюринга бинарное отношение

определяется как рефлексивное, транзитивное замыкание отношения .

Замечание 14.1.6.

Если , то для любых

и

найдутся такие

и , что .

Замечание 14.1.7.

Конфигурацию

иногда изображают сокращенно .

Замечание 14.1.8.

Машины Тьюринга можно изображать в~виде диаграмм. При этом каждое состояние обозначается кружком, а переход - стрелкой. Каждое начальное состояние распознается по ведущей в него короткой стрелке. Каждое заключительное состояние отмечается на диаграмме двойным кружком. Стрелка с пометкой a:ck, ведущая из p в q, показывает, что

является переходом данной машины Тьюринга. Обычно на диаграммах вместо чисел -1, 0, 1 (обозначающих движение влево, стояние на месте, движение вправо) используются буквы L, N, R соответственно.

Пример 14.1.9.

Рассмотрим машину Тьюринга

где , , , , , ,

Можно проверить, что для любого

выполняется следующее:

Определение 14.1.10.

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

называется детерминированной, если множество I содержит ровно один элемент и для каждой пары

существует не более одной тройки

со свойством .

Пример 14.1.11

Машина Тьюринга из примера 14.1.9 является детерминированной.



Содержание раздела