Машина Тьюринга только для чтения - Read-only Turing machine

А машина Тьюринга только для чтения или двусторонний детерминированный конечный автомат (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 г в Q, ~ г neq т}$ это отклонить состояние.

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

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

Варианты

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

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

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

Приложения

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

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

Смотрите также

внешняя ссылка

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

[1] Козен, Декстер К. (1997) [1951]. Дэвид Грис, Фред Б. Шнайдер (ред.). Автоматы и вычислимость (твердый переплет). Тексты для бакалавров по информатике (1-е изд.). Нью-Йорк: Springer-Verlag. стр.158, 210, 224. ISBN 978-0-387-94907-9.

[2] Вычислительная сложность Вагнера и Вексунга, раздел 13.3 (1986, ISBN 90-277-2146-7)

[3] Вычислительная сложность Вагнера и Вексунга, раздел 13.1 (1986, ISBN 90-277-2146-7)

[4] Kondacs, A .; Дж. Уотроус (1997). О мощности квантовых конечных автоматов. 38-й ежегодный симпозиум по основам компьютерных наук (FOCS '97). С. 66–75. CiteSeerX 10.1.1.49.6392. Дои:10.1109 / SFCS.1997.646094. ISBN 978-0-8186-8197-4. Архивировано из оригинал (– ^{Академический поиск}) на 2007-08-23. Получено 2007-11-07.

[5] Дворк, Синтия; Стокмейер, Ларри (1990). «Временной разрыв в сложности для двусторонних вероятностных конечных автоматов». SIAM Журнал по вычислениям. 19 (6): 1011–1023. Дои:10.1137/0219069. Архивировано из оригинал на 2009-10-25. Получено 2007-11-07.

[1]

[2]

[3]

[4]

[5]