Переменная машина Тьюринга - Alternating Turing machine

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

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

Определения

Неформальное описание

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

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

Формальное определение

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

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

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

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

Границы ресурсов

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

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

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

Пример

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

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

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

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

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

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

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

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

когда и . ${\ Displaystyle е (п) \ geq \ журнал (п)}$${\ Displaystyle г (п) \ geq \ журнал (п)}$

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

Ограниченное чередование

Определение

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

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

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

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

Пример

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

Сворачивающиеся классы

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

Как следствие теоремы Иммермана – Селепсеньи , иерархия логарифмического пространства схлопывается до своего первого уровня. В качестве следствия выводится иерархия рушится на его первый уровень , когда это пространство конструктивно . ${\ Displaystyle {\ mathsf {ПРОБЕЛ}} (е)}$${\ Displaystyle е = \ Омега (\ журнал)}$

Особые случаи

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

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

Рекомендации

дальнейшее чтение

• Майкл Сипсер (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.