Машина Тьюринга — это принимающее устройство, которое принимает языки (рекурсивно перечислимый набор), генерируемые грамматиками типа 0. Он был изобретен в 1936 году Аланом Тьюрингом.
Определение
Машина Тьюринга (ТМ) — это математическая модель, которая состоит из ленты бесконечной длины, разделенной на ячейки, в которые вводятся данные. Он состоит из головы, которая читает входную ленту. Государственный реестр хранит состояние машины Тьюринга. После прочтения входного символа он заменяется другим символом, его внутреннее состояние изменяется, и он перемещается из одной ячейки вправо или влево. Если TM достигает конечного состояния, входная строка принимается, в противном случае отклоняется.
ТМ можно формально описать как 7-кортеж (Q, X, ∑, δ, q 0 , B, F), где —
-
Q — конечное множество состояний
-
X это ленточный алфавит
-
∑ является входным алфавитом
-
δ — переходная функция; δ: Q × X → Q × X × {Сдвиг влево, сдвиг вправо}.
-
q 0 — начальное состояние
-
B — это пустой символ
-
F — множество конечных состояний
Q — конечное множество состояний
X это ленточный алфавит
∑ является входным алфавитом
δ — переходная функция; δ: Q × X → Q × X × {Сдвиг влево, сдвиг вправо}.
q 0 — начальное состояние
B — это пустой символ
F — множество конечных состояний
Сравнение с предыдущим автоматом
В следующей таблице показано сравнение того, как машина Тьюринга отличается от Finite Automaton и Pushdown Automaton.
| Машина | Структура данных стека | Детерминированный? |
|---|---|---|
| Конечный Автомат | Не Доступно | да |
| Pushdown Автомат | Последний вошел первый (ЛИФО) | нет |
| Машина Тьюринга | Бесконечная лента | да |
Пример машины Тьюринга
Машина Тьюринга M = (Q, X, ∑, δ, q 0 , B, F) с
- Q = {q 0 , q 1 , q 2 , q f }
- X = {a, b}
- ∑ = {1}
- q 0 = {q 0 }
- B = пустой символ
- F = {q f }
δ определяется как —
| Лента символ алфавита | Текущее состояние ‘q 0 ‘ | Современное состояние ‘q 1 ‘ | Современное состояние ‘q 2 ‘ |
|---|---|---|---|
| 1Rq 1 | 1Lq 0 | 1 литр ф | |
| б | 1Lq 2 | 1Rq 1 | 1Rq f |
Здесь переход 1Rq 1 подразумевает, что символ записи равен 1, лента движется вправо, а следующее состояние — q 1 . Аналогично, переход 1Lq 2 подразумевает, что символ записи равен 1, лента перемещается влево, а следующее состояние — q 2 .
Пространственно-временная сложность машины Тьюринга
Для машины Тьюринга под сложностью времени понимается мера количества перемещений ленты, когда машина инициализируется для некоторых входных символов, а сложность пространства — это количество ячеек записанной ленты.
Временная сложность всех разумных функций —
T (n) = O (n log n)
Пространственная сложность ТМ —
S (n) = O (n)