Машина Тьюринга только для чтения

Только для чтения машины Тьюринга или двухсторонняя детерминированный конечный автомат состояния (2DFA) является класс моделей вычислимости , которые ведут себя как стандартные машины Тьюринга и может перемещаться в обоих направлениях через вход, за исключением того, не может записать его на входной ленте. Машина в своей голой форме эквивалентна детерминированному конечному автомату по вычислительной мощности и, следовательно, может анализировать только обычный язык .

Теория [ править ]

Определим стандартную машину Тьюринга набором из 9

${\ Displaystyle M = (Q, \ Sigma, \ Gamma, \ vdash, \ _, \ delta, s, t, r)}$ куда

• ${\ displaystyle Q}$- конечный набор состояний ;
• ${\ displaystyle \ Sigma}$- конечное множество входного алфавита ;
• ${\ displaystyle \ Gamma}$- конечный ленточный алфавит ;
• ${\ displaystyle \ vdash \ in \ Gamma - \ Sigma}$это левый маркер конца ;
• ${\ displaystyle \ _ \ in \ Gamma - \ Sigma}$это пустой символ ;
• ${\ displaystyle \ delta: Q \ times \ Gamma \ rightarrow Q \ times \ Gamma \ times \ {L, R \}}$- функция перехода ;
• ${\ displaystyle s \ in Q}$это начальное состояние ;
• ${\ displaystyle t \ in Q}$это принимает состояние ;
• ${\displaystyle r\in Q,~r\neq t}$это отвергает состояние .

Таким образом, для данного символа чтения начального состояния у нас есть переход, который заменяет на , переходит в состояние и перемещает «читающую головку» в направлении (влево или вправо) для чтения следующего ввода. ^[1] В нашей машине с 2DFA только для чтения, однако, всегда.${\displaystyle q}$${\displaystyle a}$${\displaystyle \delta (q,a)=(q_{2},a_{2},d)}$${\displaystyle a}$${\displaystyle a_{2}}$${\displaystyle q_{2}}$${\displaystyle d}$${\displaystyle a=a_{2}}$

Эта модель теперь эквивалентна DFA. Доказательство включает построение таблицы, в которой перечислены результаты обратного отслеживания с элементом управления в любом заданном состоянии; в начале вычисления это просто результат попытки пройти мимо левого маркера конца в этом состоянии. При каждом движении вправо таблица может обновляться с использованием старых значений таблицы и символа, который был в предыдущей ячейке. Поскольку исходный элемент управления головкой имел некоторое фиксированное количество состояний, а в ленточном алфавите есть фиксированное количество состояний, таблица имеет фиксированный размер и, следовательно, может быть вычислена другим конечным автоматом. Однако этой машине никогда не придется возвращаться, и, следовательно, она является DFA.

Варианты [ править ]

Несколько вариантов этой модели также эквивалентны DFA. В частности, недетерминированный случай (в котором переход из одного состояния может происходить в несколько состояний с одним и тем же входом) можно свести к DFA.

Другие варианты этой модели допускают большую вычислительную сложность . С одним бесконечным стеком модель может анализировать (по крайней мере) любой язык, вычисляемый машиной Тьюринга за линейное время . ^[2] В частности, язык {a ⁿ b ⁿ c ⁿ } может быть проанализирован с помощью алгоритма, который сначала проверяет, что есть одинаковое количество a и b, затем перематывает и проверяет, что есть одинаковое количество b и c. . С дополнительной помощью недетерминизма машина может анализировать любой контекстно-свободный язык . С двумя бесконечными стеками машина эквивалентна Тьюрингу и может анализировать любые рекурсивныеформальный язык .

Если машине разрешено иметь несколько головок магнитной ленты, она может анализировать любой язык L или NL в зависимости от того, разрешен ли недетерминизм. ^[3]

Приложения [ править ]

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

В современных исследованиях модель стала важной при описании нового класса сложности квантовых конечных автоматов или детерминированных вероятностных автоматов . ^{[4] [5]}

См. Также [ править ]

• Вычислимость
• Эквиваленты машины Тьюринга
• Штабелеукладчик
• Автомат очереди
• Квантовый компьютер

Ссылки [ править ]

Внешние ссылки [ править ]

• Лекция Адама Уэббера о конечных автоматах