# Máquinas de Turing equivalentes

Uma máquina de Turing é um dispositivo teórico com uma capacidade de memória infinita, inicialmente concebida por Alan Turing em 1936. A máquina manipula símbolos em células de uma fita potencialmente infinita de acordo com uma função de transição, e pode ser adaptada para simular a lógica de qualquer algoritmo de computador.
Embora nenhum dos seguintes modelos tenha sido demonstrado ter mais poder que o modelo de máquina de Turing de uma fita — infinita e multi-símbolo —, seus autores definiram e usaram tais máquinas para investigar questões e resolver problemas mais facilmente do que eles poderiam ter ao usar o modelo tradicional da máquina de Turing.

## Máquinas equivalentes ao modelo da Máquina de Turing

Turing-equivalência
Muitas máquinas que possam ser imaginadas a ter maior capacidade computacional do que uma simples máquina de Turing universal podem ser mostradas não ter mais poder (Hopcroft and Ullman p. 159, cf Minsky). Elas podem computar mais rapidamente, ou talvez usar menos memória, ou o seu conjunto de instruções pode ser menor, mas elas não podem computar de forma mais poderosa (i.e. mais funções matemáticas). (A tese de Church-Turing levanta a seguinte hipótese: tudo que pode ser “computado”, pode ser computado por alguma máquina de Turing).
Os modelos de máquina sequencial
Todos os modelos a seguir são chamados de "modelos de máquina sequencial" para distingui-los dos "modelos de máquina paralela" (van Emde Boas (1990) p. 18).

## Máquinas de Turing baseadas em Fita
### Máquinas de uma fita com símbolos e/ou instruções restritos

Os seguintes modelos são máquinas de Turing de fita única, mas restringidos com (i) símbolos de fita restritos { "marcado", "desmarcado" }, e/ou (ii) instruções sequenciais e/ou (iii) ações de máquina completamente atomizadas.

#### Modelo de computação "Formulação 1" de Post

Emil Post (1936) em uma descrição independente de um processo computacional, reduziu os símbolos permitidos ao conjunto binário equivalente de marcas na fita { "marcado", "desmarcado"=vazio}. Ele mudou a noção de "fita", partindo de uma fita infinita pelo lado direito para um conjunto infinito de caixas, cada uma com um conjunto de instruções para ambas as direções. Ele atomizou as 5-uplas de Turing em instruções de 4-uplas separadas das instruções de imprimir/apagar símbolos. Embora seu (1936) modelo seja ambíguo em respeito a isso, o modelo de Post (1947) não exige a execução de instruções sequenciais.
Seu modelo extremamente simples pode simular qualquer máquina de Turing, e embora sua "Formulação 1" de 1936 não use a palavra "programa" ou "máquina", ela é efetivamente uma formulação de um computador programável muito primitivo e associada a linguagem de programação, com ações em caixas como uma memória ilimitada e o conjunto de instruções constituindo um programa.

#### Máquinas Wang

Em um influente artigo, Hao Wang (1954, 1957) reduziu a "formulação 1" de Post para máquinas que ainda usam uma fita binária infinita pelos dois lados, mas cujas instruções são mais simples — sendo os componentes "atômicos" das instruções de Post — e são por padrão executadas sequencialmente (como um "programa de computador"). Seu principal objetivo declarado foi o de oferecer, como uma alternativa a teoria de Turing, uma que é "mais econômica em operações básicas". Seus resultados são "formulações de programas" de uma variedade de tais máquinas, incluindo a máquina de Wang-W com o conjunto de instruções
    { DESLOCA-ESQUERDA, DESLOCA-DIREITA, MARCA-QUADRADO, APAGA-QUADRADO, PULE-SE-QUADRADO-MARCADO-PARA xxx }
e seu ainda mais reduzido conjunto com 4 instruções da Máquina Wang-b
    { DESLOCA-ESQUERDA, DESLOCA-DIREITA, MARCA-QUADRADO, PULE-SE-QUADRADO-MARCADO-PARA xxx }
que não tem sequer uma instrução APAGA-QUADRADO.
Muitos autores mais tarde introduziram variantes das máquinas discutidas por Wang:
Minsky (1961) evoluiu a noção de Wang com sua versão de modelo de "máquina contadora" (multi-fita) que permitiu os movimentos de DESLOCA-ESQUERDA e DESLOCA-DIREITA de cabeças separadas mas não imprimindo em todas elas. Neste caso, as fitas seriam não-finitas pelo lado esquerda, onde cada fim é marcado com uma única "marca" para indicar o final. Ele foi capaz de reduzir isso para uma única fita, mas à custo da introdução de movimentos de multi-fita equivalentes para multiplicação e divisão em vez do muito mais simples { DESLOCA-ESQUERDA = DECREMENTA, DESLOCA-DIREITA = INCREMENTA }.
Davis, adicionando uma instrução explícita PARE (Halt) em uma das máquinas discutidas por Wang, utilizou um modelo com o conjunto de instruções
    { DESLOCA-ESQUERDA, DESLOCA-DIREITA, APAGA, MARCA, PULE-SE-QUADRADO-MARCADO-PARA xxx, PULE-PARA xxx, PARE }
e também tendo considerado versões com alfabetos de fita de tamanho maior do que 2.

#### Linguagem Teórica P" de Böhm

De acordo com o projeto de Wang para buscar uma teoria Turing-equivalente que seja "econômica em operações básicas", e desejando evitar saltos incondicionais, uma notável linguagem teórica é a linguagem P'', de 4 instruções, introduzida por Corrado Böhm em 1964 — a primeira linguagem de "programação estruturada" imperativa, "sem GOTO", a ser provada Turing completa.

### Máquinas de Turing multi-fita

Em análise prática, vários tipos de máquinas de Turing multi-fita são frequentemente utilizados. Máquinas multi-fitas são semelhantes às máquinas com uma única fita, mas há um número constante k de fitas independentes.
A função de transição tem controle independente total sobre todas as cabeças, incluindo qualquer movimento e escrita de símbolos em suas próprias fitas (cf Aho-Hopcroft-Ullman 1974 p. 26). A maioria dos modelos tem fitas não-finitas pelo lado esquerdo, e finitas pelo lado direito.
Este modelo intuitivamente parece ser muito mais poderoso que o modelo de uma única fita, mas qualquer máquina multi-fita, não importa quão grande seja o k, pode ser simulada por uma máquina com uma única fita usando apenas um tempo quadraticamente maior (Papadimitriou 1994, Thrm 2.1.). Assim, máquinas multi-fitas não podem calcular quaisquer funções a mais que as máquinas de fita única, e nenhuma das classes robustas de complexidade (tal como tempo polinomial) são afetadas por uma mudança entre máquinas de fita única e multi-fita.

#### Máquina de Turing de duas pilhas

Máquinas de Turing de duas pilhas tem uma entrada de somente leitura e duas fitas de armazenamento. Se uma cabeça se mover para a esquerda de qualquer fita, um "branco" é impresso nesta fita, mas um símbolo de uma "biblioteca" também pode ser impresso.

#### Definição formal: máquina de Turing multi-fita

Uma máquina de Turing de k-fitas pode ser descrita como uma 6-upla $M=\langle Q,\Gamma ,s,b,F,\delta \rangle$ onde
* $Q$ é um conjunto finito de estados
* $\Gamma$ é um conjunto finito de alfabeto da pilha
* $s\in Q$ é o estado inicial
* $b\in \Gamma$ é o simbolo em branco
* $F\subseteq Q$ é o conjunto de estados de aceitação ou rejeição
* $\delta :Q\times \Gamma ^{k}\rightarrow Q\times (\Gamma \times \{L,R,S\})^{k}$ é uma função parcial chamada de função de transição, onde L é deslocamento à esquerda, R é deslocamento à esquerda, S é nenhum deslocamento.

### Máquinas de Turing determinísticas e não-determinísticas

Se a função de transição tiver exatamente uma entrada para cada combinação de símbolo e estado, então a máquina é uma "Máquina de Turing determinística" (MTD). Se a função de transição contiver múltiplas entradas para uma combinação de símbolo e estado, então a máquina é uma "Máquina de Turing não-determinística" (MTN). Os dois são computacionalmente equivalentes, isto é, é possível transformar qualquer MTN em uma MTD (e vice-versa).

### Máquinas de turing oblivious

Uma máquina de Turing oblivious é uma máquina de Turing onde o movimento de várias cabeças são funções constantes de tempo, independente da entrada. Em outras palavras, há uma sequência pré-determinada em que várias fitas são varridas e escritas. Pippenger and Fischer (1979) mostrou que qualquer computação que pode ser executada por uma máquina de Turing multi-fita em n passos pode ser executada por uma máquina de Turing oblivious de duas fitas em O(n log n) passos.

## Máquinas com entrada entrada e saída

Qualquer uma das máquinas baseadas em fita acima pode ser equipada com fitas de entrada e saída.
É difícil estudar complexidade de espaço sublinear em máquinas multi-fita com o modelo tradicional, porque uma entrada de tamanho n já toma um espaço n. Assim, para estudar pequenas classes DSPACE, nós devemos usar um modelo diferente. Em certo sentido, se nós nunca escrevemos na fita de entrada, nós não queremos carregar a máquina com esse espaço. E se nós nunca lemos da nossa fita de saída, nós também não queremos carregar a máquina com esse espaço.
Nós resolvemos esse problema ao introduzir uma máquina de Turing de k-cadeia com entrada e saída. Isso é o mesmo que uma máquina de Turing de k-cadeia ordinária, exceto que a função de transição $\delta$ é limitada, de modo que a fita de entrada nunca pode ser alterada, e assim como a cabeça de saída nunca pode se mover para a esquerda. Este modelo nos permite definir classes de espaço determinísticas menores do que a linear. Máquinas de Turing com entrada-e-saída também tem a mesma complexidade de tempo que as outras máquinas de Turing; em outras palavras de Papaditriou 1994 Prop 2.2:
    Para qualquer máquina de Turing de k-cadeia M operando dentro do limite de tempo f(n)), há uma máquina de Turing de (k+2)-cadeia com entrada e saída que opera dentro do limite de tempo O(f(n)).
Máquinas de Turing de k-cadeia com entrada e saída são frequentemente usadas em definições formais de recursos de complexidade DSPACE em, por exemplo, Papadimitriou 1994 (Def. 2.6).

## Outras máquinas equivalentes e métodos

* Máquina de Turing multidimensional: Por exemplo, um modelo de Schönhage (1990) usa as quatro instruções de movimentos de cabeça { Norte, Sul, Leste, Oeste }.
* Máquina de Turing de uma fita e multi-cabeça: Em uma prova de indecidibilidade do "problema da etiqueta", Minsky (1961) e Shepherdson and Sturgis (1963) descreveram máquinas com uma única fita que poderia escrever ao longo da fita com uma única cabeça e ler adicionalmente ao longo da fita com uma outra cabeça.
* Algoritmo de Markov (1960) é outro notável modelo computacional simples, baseado na reescrita de cadeias, equivalente à máquinas de Turing.
* Cálculo Lambda
* Autômato de fila
* Modelos de máquina de registro