Переменная машина Тьюринга

Машины Тьюринга
Машина
Эквиваленты машины Тьюринга Примеры машины Тьюринга Галерея машин Тьюринга
Варианты
Переменная машина Тьюринга Нейронная машина Тьюринга Недетерминированная машина Тьюринга Квантовая машина Тьюринга Машина Пост-Тьюринга Вероятностная машина Тьюринга Машина Тьюринга только для чтения Право движущиеся машины Тьюринга только для чтения Многолента машина Тьюринга Многодорожечная машина Тьюринга Симметричная машина Тьюринга Общая машина Тьюринга Однозначная машина Тьюринга Универсальная машина Тьюринга Зенон машина
Наука
Алан Тьюринг Категория: машина Тьюринга
v т е

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Май 2011 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В теории сложности вычислений , Переменный машин Тьюринга ( ATM ) является недетерминирована машиной Тьюринга ( НТМ ) с правилом принятия вычисления, обобщающими правилами , используемых в определении классов сложности NP и со-NP . Концепция банкомата была изложена Чандрой и Стокмейером ^[1] и независимо Козеном ^[2] в 1976 году с совместной публикацией в журнале в 1981 году ^[3].

Определения [ править ]

Неофициальное описание [ править ]

Определение NP использует экзистенциальный способ вычисления: если какой-либо выбор приводит к состоянию принятия, то все вычисления принимаются. Определение co-NP использует универсальный режим вычислений: только если все варианты приводят к состоянию принятия, все вычисления принимаются. Альтернативная машина Тьюринга (или, точнее, определение принятия для такой машины) чередуется между этими режимами.

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

Формальное определение [ править ]

Формально (однопленочная) чередующаяся машина Тьюринга - это кортеж из 5 элементов, в котором $M=(Q,\Gamma ,\delta ,q_{0},g)$

$Q$ конечный набор состояний
$\Gamma$ конечный ленточный алфавит
$\delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})$ называется функцией перехода ( L сдвигает голову влево, а R сдвигает голову вправо)
$q_{0}\in Q$ это начальное состояние
$g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}$ указывает тип каждого состояния

Если M находится в состоянии с, то эта конфигурация считается принимающей , а если конфигурация - отклоняющей . Конфигурация с считается принимающей, если все конфигурации, достижимые на одном шаге, принимаются, и отклоняется, если некоторая конфигурация, достижимая на одном шаге, отклоняется. Конфигурация с называется принимающей, когда существует некоторая конфигурация, достижимая на одном шаге, которая принимает и отклоняет, когда все конфигурации, достижимые на одном шаге, отклоняются (это тип всех состояний в NTM). Говорят, что M принимает входную строку w, если начальная конфигурация M $q\in Q$ $g(q)=accept$ $g(q)=reject$ $g(q)=\wedge$ $g(q)=\vee$ (состояние M - головка находится на левом конце ленты, а лента содержит w ) принимает и отклоняет, если исходная конфигурация отклоняет. $q_{0}$

Границы ресурса [ править ]

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

Банкомат вовремя выбирает формальный язык, если для любого ввода длины $n достаточно$ изучить конфигурации только до шагов, чтобы пометить начальную конфигурацию как принимающую или отклоняющую. Банкомат выбирает язык в пространстве, если достаточно проверки конфигураций, которые не изменяют ячейки ленты за пределами ячейки слева. $t(n)$ $t(n)$ $s(n)$ $s(n)$

Говорят, что язык, определенный банкоматом во времени для некоторой константы, находится в классе , а язык, определенный в пространстве , называется принадлежащим классу . $c\cdot t(n)$ $c>0$ ${\mathsf {ATIME}}(t(n))$ $c\cdot s(n)$ ${\mathsf {ASPACE}}(s(n))$

Пример [ править ]

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

Такая машина решает количественные булевы формулы во времени и пространстве . $n^{2}$ $n$

Проблема логической выполнимости может рассматриваться как частный случай, когда все переменные экзистенциально определены количественно, что позволяет обычному недетерминизму, который использует только экзистенциальное ветвление, эффективно решать ее.

Классы сложности и сравнение с детерминированными машинами Тьюринга [ править ]

Для банкоматов полезно определить следующие классы сложности :

${\mathsf {AP}}=\bigcup _{k>0}{\mathsf {ATIME}}(n^{k})$ являются ли языки разрешимыми за полиномиальное время
${\mathsf {APSPACE}}=\bigcup _{k>0}{\mathsf {ASPACE}}(n^{k})$ являются ли языки разрешимыми в полиномиальном пространстве
${\mathsf {AEXPTIME}}=\bigcup _{k>0}{\mathsf {ATIME}}(2^{n^{k}})$ являются ли языки разрешимыми за экспоненциальное время

Они аналогичны определениям P , PSPACE и EXPTIME , учитывая ресурсы, используемые банкоматом, а не детерминированной машиной Тьюринга. Чандра, Козен и Штокмейер ^[3] доказали теоремы

ALOGSPACE = P
AP = PSPACE
APSPACE = EXPTIME
AEXPTIME = EXPSPACE
${\mathsf {ASPACE}}(f(n))=\bigcup _{c>0}{\mathsf {DTIME}}(2^{cf(n)})={\mathsf {DTIME}}(2^{O(f(n))})$
${\mathsf {ATIME}}(g(n))\subseteq {\mathsf {DSPACE}}(g(n))$
${\mathsf {NSPACE}}(g(n))\subseteq \bigcup _{c>0}{\mathsf {ATIME}}(c\times g(n)^{2}),$

когда и . $f(n)\geq \log(n)$ $g(n)\geq \log(n)$

Более общая форма этих отношений выражается тезисом о параллельных вычислениях .

Ограниченное чередование [ править ]

Определение [ править ]

В этом разделе не процитировать любые источники . Пожалуйста, помогите улучшить этот раздел , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален . ( Октябрь 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Переменный машин Тьюринга с K чередованием представляет собой чередующаяся машина Тьюринга , которая переключается с экзистенциальным универсальным состоянием или наоборот не более чем K -1 раз. (Это чередующаяся машина Тьюринга, состояния которой разделены на k множеств. Состояния в множествах с четными номерами универсальны, а состояния в множествах с нечетными номерами являются экзистенциальными (или наоборот). Машина не имеет переходов между состояниями в множестве i и состояние в множестве j < i .)

${\mathsf {ATIME}}(C,j)=\Sigma _{j}{\mathsf {TIME}}(C)$ - это класс функций во времени, начинающийся с экзистенциального состояния и в большинстве случаев чередующийся . Это называется $j-$ м уровнем иерархии. $f\in C$ $j-1$ ${\mathsf {TIME}}(C)$

${\mathsf {coATIME}}(C,j)=\Pi _{j}{\mathsf {TIME}}(C)$ это те же классы, но начиная с универсального состояния, это дополнение языка . ${\mathsf {ATIME}}(f,j)$

${\mathsf {ASPACE}}(C,j)=\Sigma _{j}{\mathsf {SPACE}}(C)$ аналогично определяется для вычислений с ограниченным пространством.

Пример [ править ]

Рассмотрим задачу минимизации цепи : дана схема вычисления булевой функции п и число п , определить, есть ли цепь с не более п ворот , который вычисляет ту же функцию п . Альтернативная машина Тьюринга с одним чередованием, начиная с экзистенциального состояния, может решить эту проблему за полиномиальное время (угадав схему B с не более чем n вентилями, затем переключившись в универсальное состояние, угадав вход и проверив, что выход of B на этом входе совпадает с выводом A на этом входе).

Сворачивающиеся классы [ править ]

Говорят, что иерархия сворачивается до уровня $j,$ если каждый язык на уровне иерархии находится на своем уровне $j$ . $k\geq j$

Как следствие теоремы Иммермана – Селепсеньи , иерархия логарифмического пространства схлопывается до своего первого уровня. ^[4] В качестве следствия выводится иерархия падает на ее первый уровень , когда это пространство построимо ^[^{править}^] . ${\mathsf {SPACE}}(f)$ $f=\Omega (\log )$

Особые случаи [ править ]

Переменная машина Тьюринга за полиномиальное время с k чередованиями, начиная с экзистенциального (соответственно универсального) состояния, может решить все проблемы в классе (соответственно ). ^[5] Эти классы иногда обозначаются и соответственно. Подробнее см. Статью о полиномиальной иерархии . $\Sigma _{k}^{p}$ $\Pi _{k}^{p}$ $\Sigma _{k}{\rm {P}}$ $\Pi _{k}{\rm {P}}$

Другой частный случай иерархии времени - логарифмическая иерархия .

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

^ Чандра, Ашок К .; Стокмейер, Ларри Дж. (1976). «Чередование». Proc. 17-й симпозиум IEEE. по основам информатики . Хьюстон, Техас. С. 98–108. DOI : 10,1109 / SFCS.1976.4 .
Перейти ↑ Kozen, D. (1976). «О параллелизме в машинах Тьюринга». Proc. 17-й симпозиум IEEE. по основам информатики . Хьюстон, Техас. С. 89–97. DOI : 10,1109 / SFCS.1976.20 . hdl : 1813/7056 .
^ а б Чандра, Ашок К .; Kozen, Dexter C .; Стокмейер, Ларри Дж. (1981). «Чередование» (PDF) . Журнал ACM . 28 (1): 114–133. DOI : 10.1145 / 322234.322243 . Архивировано из оригинального (PDF) 12 апреля 2016 года.
^ Иммерман, Нил (1988). «Недетерминированное пространство закрыто при дополнении» (PDF) . SIAM Journal on Computing . 17 (5): 935–938. CiteSeerX 10.1.1.54.5941 . DOI : 10.1137 / 0217058 .
Перейти ↑ Kozen, Dexter (2006). Теория вычислений . Springer-Verlag . п. 58 . ISBN 9781846282973.

Дальнейшее чтение [ править ]

Майкл Сипсер (2006). Введение в теорию вычислений, 2-е изд . PWS Publishing. ISBN 978-0-534-95097-2. Раздел 10.3: Чередование, стр. 380–386.
Христос Пападимитриу (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. ISBN 978-0-201-53082-7. Раздел 16.2: Чередование, стр. 399–401.
Бахадыр Хусаинов; Анил Нероде (2012). Теория автоматов и ее приложения . Springer Science & Business Media. ISBN 978-1-4612-0171-7.

[chasto-1] Чандра, Ашок К .; Стокмейер, Ларри Дж. (1976). «Чередование». Proc. 17-й симпозиум IEEE. по основам информатики . Хьюстон, Техас. С. 98–108. DOI : 10,1109 / SFCS.1976.4 .

[kozen-2] Перейти ↑ Kozen, D. (1976). «О параллелизме в машинах Тьюринга». Proc. 17-й симпозиум IEEE. по основам информатики . Хьюстон, Техас. С. 89–97. DOI : 10,1109 / SFCS.1976.20 . hdl : 1813/7056 .

[alternation-3] а б Чандра, Ашок К .; Kozen, Dexter C .; Стокмейер, Ларри Дж. (1981). «Чередование» (PDF) . Журнал ACM . 28 (1): 114–133. DOI : 10.1145 / 322234.322243 . Архивировано из оригинального (PDF) 12 апреля 2016 года.

[4] Иммерман, Нил (1988). «Недетерминированное пространство закрыто при дополнении» (PDF) . SIAM Journal on Computing . 17 (5): 935–938. CiteSeerX 10.1.1.54.5941 . DOI : 10.1137 / 0217058 .

[5] Перейти ↑ Kozen, Dexter (2006). Теория вычислений . Springer-Verlag . п. 58 . ISBN 9781846282973.

[1]