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

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

Теория

Мы определяем стандартную машину Тьюринга девятикратным набором

$M=(Q,\Sigma ,\Gamma ,\vdash ,\_,\delta ,s,t,r)$ где

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

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

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

Варианты

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

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

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

Приложения

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

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

См. также

Ссылки

^ Козен, Декстер К. (1997) [1951]. Дэвид Грис, Фред Б. Шнайдер (ред.). Автоматы и вычислимость (твердый переплет). Тексты для бакалавриата по информатике (1-е изд.). Нью-Йорк: Springer-Verlag. стр. 158 , 210, 224. ISBN. 978-0-387-94907-9 .
^ Вычислительная сложность Вагнера и Вексунга, раздел 13.3 (1986, ISBN 90-277-2146-7 )
^ Вычислительная сложность Вагнера и Вексунга, раздел 13.1 (1986, ISBN 90-277-2146-7 )
^ Кондакс, А.; Дж. Уотрус (1997). «О мощности квантовых конечных автоматов». Материалы 38-го ежегодного симпозиума по основам информатики . стр. 66–75. CiteSeerX 10.1.1.49.6392 . дои : 10.1109/SFCS.1997.646094 . ISBN 978-0-8186-8197-4 . S2CID 14025116 . Архивировано из оригинала 23 августа 2007 г. Проверено 7 ноября 2007 г.
^ Дворк, Синтия ; Стокмейер, Ларри (1990). «Разрыв во временной сложности для двусторонних вероятностных автоматов с конечным состоянием» . SIAM Journal по вычислительной технике . 19 (6): 1011–1023. дои : 10.1137/0219069 . Архивировано из оригинала 28 октября 2009 г. Проверено 7 ноября 2007 г.

Внешние ссылки

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

[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] Кондакс, А.; Дж. Уотрус (1997). «О мощности квантовых конечных автоматов». Материалы 38-го ежегодного симпозиума по основам информатики . стр. 66–75. CiteSeerX 10.1.1.49.6392 . дои : 10.1109/SFCS.1997.646094 . ISBN 978-0-8186-8197-4 . S2CID 14025116 . Архивировано из оригинала 23 августа 2007 г. Проверено 7 ноября 2007 г.

[5] Дворк, Синтия ; Стокмейер, Ларри (1990). «Разрыв во временной сложности для двусторонних вероятностных автоматов с конечным состоянием» . SIAM Journal по вычислительной технике . 19 (6): 1011–1023. дои : 10.1137/0219069 . Архивировано из оригинала 28 октября 2009 г. Проверено 7 ноября 2007 г.

[1]

[2]

[3]

[4]

[5]