Математическая теория формальных языков
Машины Тьюринга
Определение 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 является детерминированной.
