# Máquina de Turing alternante

Em teoria da complexidade, uma máquina de Turing alternante (MTA) é uma máquina de Turing não determinística (MTN) com uma regra para aceitar computações que generalizam as regras usadas nas definições de Classe de complexidade NP (complexidade) e Co-NP. O conceito de MTA foi estabelecido por Chandra and Stockmeyer, em 1976 (ver referências).

## Definições
### Descrição informal

A definição de NP usa o modo existencial de computação: se alguma escolha leva para um estado de aceitação, então toda a computação é aceita. A definição de co-NP usa o modo universal de computação: só se todas as escolhas levam para um estado de aceitação, então a computação é aceita. Uma máquina de Turing alternante alterna entre esses modos.
Uma máquina de Turing alternante é uma máquina de Turing não determinística que tem os estados divididos em dois grupos: estados existenciais e estados universais. Um estado existencial é aceito se alguma transição leva pra um estado de aceitação; um estado universal é aceito se toda transição leva para um estado de aceitação. A máquina como um todo aceita se o estado inicial é aceito.

### Descrição formal

Formalmente, uma máquina de Turing alternante (de uma fita) é uma 5-Enupla $M=(Q,\Gamma ,\delta ,q_{0},g)$ onde
* $Q$ é o conjunto finito de estados
* $\Gamma$ é o alfabeto de fita
* $\delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})$ é a função de transição (L move a cabeça para a esquerda e R para a direita)
* $q_{0}\in Q$ é o estado inicial
* $g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}$ especifica o tipo de cada estado
Se M esta num estado $q\in Q$ com $g(q)=accept$ então essa configuração é dita de aceitação, e se $g(q)=reject$ entao a configuração é dita de rejeição. A configuração com $g(q)=\wedge$ é dita de aceitação se todas as configurações levam em um estado de aceitação, e de rejeição se alguma configuração leva em um estado de rejeição. Uma configuração com $g(q)=\vee$ é dita de aceitação quando existe alguma configuração que leva em um estado de aceitação e de rejeição quando todas as configuração levam em um estado de rejeição. Diz-se que M aceita uma entrada w se a configuração inicial de M (o estado de M é $q_{0}$, a cabeça está no canto esquerdo da fita e a fita contém w) é de aceitação, e que M rejeita w se a configuração inicial é de rejeição.

### Limite de recursos

Ao decidir se a configuração de uma MTA é de aceitação ou de rejeição usando a definição acima, não é necessário examinar todas as configurações que são alcançáveis a partir da configuração atual. Em particular, uma configuração existencial pode ser rotulada como de aceitação se alguma configuração seguinte é de aceitação, e uma configuração universal pode ser rotulada de rejeição se alguma configuração seguinte é de rejeição.
Uma MTA decide uma Linguagem formal em tempo $t(n)$ se, em cada entrada de tamanho $n$, examinando as configuração só acima de $t(n)$ passos é suficiente para rotular a configuração inicial como de aceitação ou de rejeição. Podemos dizer que uma MTA decide a linguagem em espaço $s(n)$ examinando se as configurações não modificam células da fita além de $s(n)$ células a partir da esquerda.
Uma linguagem que é decidida por alguma MTA em tempo $c\cdot t(n)$ por alguma constante $c>0$ está na classe ${\rm {ATIME}}(t(n))$, e uma linguagem decidida em espaço $c\cdot s(n)$ está na classe ${\rm {ASPACE}}(s(n))$.

## Classes de complexidade e comparação com máquinas de Turing determinísticas

As Classe de complexidade são úteis para definir MTAs:
* ${\rm {AP}}=\bigcup _{k>0}{\rm {ATIME}}(n^{k})$ são as linguagens decidíveis em tempo polinomial
* ${\rm {APSPACE}}=\bigcup _{k>0}{\rm {ASPACE}}(n^{k})$ são as linguagens decidíveis em espaço polinomial
* ${\rm {AEXPTIME}}=\bigcup _{k>0}{\rm {ATIME}}(k^{n})$ são as linguagens decidíveis em tempo exponencial
Estas definições são similares as de P (complexidade), PSPACE, e Exptime, considerando os recursos usados por uma MTA ao invéz de uma MTD. Chandra, Kozen, and Stockmeyer provaram esses teoremas:
* AP = PSPACE
* APSPACE = EXPTIME
* AEXPTIME = EXPSPACE
* $ASPACE(f(n))=\bigcup _{c>0}{\rm {DTIME}}(2^{cf(n)})={\rm {DTIME}}(2^{O(f(n))})$
* $ATIME(g(n))\subseteq {\rm {DSPACE}}(g(n))$
* $NSPACE(g(n))\subseteq \bigcup _{c>0}{\rm {ATIME}}(c\times g(n)^{2})$
Quando $f(n)\geq \log(n)$ e $g(n)\geq \log(n)$ Isso é expresso pela Tese da computação paralela.

## Alternância limitada
### Definição

Uma máquina de Turing alternante com k alternações é uma máquina de Turing alternante que alterna de um estado existencial para um universal ou vice e versa mais de k+1 vezes. (Essa é uma máquina de Turing alternante que os estados são divididos em k grupos. Os estados nos grupos pares são universais e os estados nos grupos ímpares são existenciais (ou vice e versa). A máquina não tem transições entre estados no grupo i e no grupo j < i.)
${\rm {ATIME}}(C,j)=\Sigma _{j}{\rm {TIME}}(C)$ é a classe de função em tempo $f\in C$ começando com um estado existencial e alternando no máximo $j-1$ vezes. Esse é chamado o $j$-ésimo nível da hierarquia ${\rm {TIME}}(C)$.
${\rm {coATIME}}(C,j)=\Pi _{j}{\rm {TIME}}(C)$ é a mesma classe, mas começando com um estado universal, é o complemento da linguagem de ${\rm {ATIME}}(f,j)$.
${\rm {ASPACE}}(C,j)=\Sigma _{\rm {SPACE}}(C)$ é definido similarmente para cálculo de espaço delimitado.

### Classes em colapso

É dito que o colapso hierárquico para o nível $j$ se toda linguagem no nível $k\geq j$ de uma hierarquia está no nível $j$.
Como o corolário de Immerman–Szelepcsényi theorem, o colapso da hierarquia de espaço logaritmântico para o primeira nível. Como o corolário o colapso da hierarquia ${\rm {SPACE}}(f)$ pro primeira level quando $f=\Omega (\log )$ é uma Função construível

### Classes especiais

Uma máquina de Turing alternante em tempo polinomial com k alternâncias, começando num estado existencial pode decidir todos os problemas na classe $\Sigma _{k}{\rm {P}}$ (respectivamente, $\Pi _{k}{\rm {P}}$).
Outro caso especial de hierarquia de tempo é logarithmic hierarchy.