Введение в машину Тьюринга
Машина Тьюринга - это принимающее устройство, которое принимает языки (рекурсивно перечисляемый набор), сгенерированные грамматиками типа 0. Он был изобретен в 1936 году Аланом Тьюрингом.
Определение
Машина Тьюринга (TM) - это математическая модель, которая состоит из ленты бесконечной длины, разделенной на ячейки, в которые вводятся данные. Он состоит из головки, которая считывает входную ленту. В регистре состояний хранится состояние машины Тьюринга. После считывания входного символа он заменяется другим символом, его внутреннее состояние изменяется, и он перемещается из одной ячейки вправо или влево. Если TM достигает конечного состояния, вводимая строка принимается, в противном случае отклоняется.
TM можно формально описать как набор из семи (Q, X, ∑, δ, q 0 , B, F), где -
Q конечный набор состояний
X ленточный алфавит
∑ это входной алфавит
δ- функция перехода; δ: Q × X → Q × X × {Сдвиг влево, Сдвиг вправо}.
q0 это начальное состояние
B это пустой символ
F это набор конечных состояний
Сравнение с предыдущим автоматом
В следующей таблице показано сравнение того, чем машина Тьюринга отличается от конечного автомата и выталкивающего автомата.
| Машина | Структура данных стека | Детерминированный? |
|---|---|---|
| Конечный автомат | NA | да |
| Выталкивающий автомат | Последний пришел - первый ушел (LIFO) | Нет |
| Машина Тьюринга | Бесконечная лента | да |
Пример машины Тьюринга
Машина Тьюринга 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 | 1Lq f |
| б | 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)