Введение в машину Тьюринга

Машина Тьюринга - это принимающее устройство, которое принимает языки (рекурсивно перечисляемый набор), сгенерированные грамматиками типа 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)