O artigo máquina de Turing fornece uma introdução geral da máquina de Turing, enquanto este artigo cobre uma classe específica de máquina de Turing.
A máquina de Post-Turing é uma "formulação de um programa" de um tipo especialmente simples de máquina de Turing, compreendendo uma variante do modelo de computação Turing-equivalente de Emil Post descrito abaixo. (O modelo de Post e o modelo de Turing, embora muito semelhantes, foram desenvolvidos independentemente. O artigo de Turing foi recebido para publicação em Maio de 1936, seguido pelo artigo de Post enviado em Outubro.) Uma máquina de Post–Turing usa um alfabeto binário, uma sequência infinita de locais de armazenamento binário, e uma linguagem de programação primitiva com instruções para movimentação bi-direcional entre os locais de armazenamento e alteração de seus conteúdos a cada movimento. O nome "programa de Post–Turing" e "máquina de Post–Turing" foram utilizados por Martin Davis em 1973–1974 (Davis 1973, p.69ff). Mais tarde, em 1980, Davis utilizou o nome "programa de Turing–Post" (Davis, em Steen, p. 241).
1936: Modelo de Post Em seu artigo de 1936, '"Finite combinatory processes—formulation 1"' - Processos combinatórios finitos, formulação 1 - (que pode ser encontrado na página 289 de The Undecidable), Emil Post descreveu um modelo de extrema simplicidade que ele conjecturou como "logicamente equivalente a uma função recursiva", o que foi comprovado mais tarde. As citações seguintes são deste artigo.
O modelo de computação de Post difere do modelo da máquina de Turing em uma atomização nas ações que um "computador humano" realizaria durante a computação.
O modelo de Post emprega um espaço infinito de símbolos que consiste de uma "sequência infinita bidirecional de espaços ou caixas", com cada caixa capaz de estar em qualquer uma das duas condições possíveis condições, ou seja, "marcada" (como por um simples traço vertical) e "desmarcado" (vazio). Inicialmente, finitamente, algumas das caixas são marcadas, e o restante permanece desmarcado. Um "trabalhador" deve então se mover entre as caixas, estando e operando em apenas uma caixa por vez, de acordo com um conjunto fixo e finito de direções (instruções), que são numeradas em ordem (1,2,3,...,n). Começando por uma caixa "sinalizada como ponto de partida", o "trabalhador" segue o conjunto de instruções, uma de cada vez, começando pela instrução 1.
As instruções podem exigir que o "trabalhador" execute as seguintes "ações básicas" ou "operações":
(a) Marque a caixa em que ele está (assuma que está vazio), (b) Apague a marcação na caixa em que ele está (assuma que está marcada), (c) Mova-o para a caixa a sua direita , (d) Mova-o para a caixa a sua esquerda, (e) Determine se a caixa em que ele está, está marcada ou não.
Especificamente, a i-ésima direção (instrução) dada ao trabalhador deve ter um dos seguintes formatos:
(A) Execute a operação Oi [Oi = (a), (b), (c) ou (d)] e então siga a direção ji, (B) Execute a operação (e) e de acordo com a resposta sim ou não correspondente, siga a direção ji' ou ji' ' , (C) Pare.
(O texto recuado e em itálico acima estão como no original.) Post observou que esta formulação está "em seus estados iniciais" de desenvolvimento, e mencionou várias possibilidades de "maior flexibilidade" em sua forma final definitiva, incluindo: (1) substituir a infinidade de caixas por um espaço finito, mas extensível, de símbolos, "estendendo as operações primitivas para permitir a extensão necessária do espaço finito de símbolos dados para o processo prosseguir", (2) usar um alfabeto de mais de dois símbolos, "tem mais que um caminho de marcar uma caixa", (3) introduzir finitamente muitos "objetos físicos que funcionam como ponteiros, os quais o "trabalhador" pode identificar e mover de uma caixa a outra.".
1947: Redução formal de Post das 5-tuplas de Turing para 4-tuplas
Como mencionado brevemente no artigo máquina de Turing, Post, em seu artigo de 1947 (Recursive Unsolvability of a Problem of Thue - Insolubilidade recursiva do problema de Thue) atomizou as 5-tuplas de Turing a 4-tuplas: "Nossas quádruplas são quíntuplas no desenvolvimento de Turing. Isto é, onde nossa instrução padrão ordena ou uma impressão (impressão sobreposta) ou movimentos, esquerda ou direita, a instrução padrão de Turing sempre ordena uma impressão e um movimento, direita, esquerda, ou nenhum"(nota de rodapé 12, Undecidable p. 300)
Como Turing, ele definiu "apagar" como a impressão de um símbolo "S0". E assim, seu modelo admitiu quádruplas de somente três tipos (cf p. 294 Undecidable): qi Sj L ql, qi Sj R ql, qi Sj Sk ql
Nesse momento ele ainda mantinha a máquina de estados pela convenção de Turing - ele não havia formalizado a noção de uma suposta sequência definida de passos até que um teste específico de um símbolo "desviou" a execução para outro destino.
1954, 1957: Modelo Wang
Wang (1957, mas apresentado a ACM em 1954) é frequentemente citado (cf Minsky (1967) p. 200) como a fonte da formulação da programa da máquina de Turing dupla-fita usando instruções numeradas a partir do conjunto:
escreva 0 escreva 1 mova para esquerda mova para direita Se valor encontrado é 0 então vá para a instrução i Se valor encontrado é 1 então vá para a instrução j
onde uma execução sequencial é assumida, e um simples "if ... then ... else" de Turing é "atomizado" em duas declarações "if ... then ...". (Aqui '1' e '0' são usados onde Wang "marcou" e "desmarcou", respectivamente, e assume-se que a fita inicial contém somente '0's exceto se existirem finitos '1's.)
Wang observou o seguinte: "Já que não há instrução separada para halt (parar), entende-se que a máquina irá parar quando chegar numa etapa em que o programa não contém instruções dizendo o que a máquina deve fazer em seguida." (p.65) "Em contraste com Turing, que utilizou uma fita unidirecional infinita que tem um começo, nós estamos seguindo Post no uso de uma fita bidirecional infinita." (p. 65) Incondicionais "gotos" são facilmente derivados das instruções acima, então "nós podemos utilizá-los livremente também". (p.84)
Qualquer máquina de Turing dupla-fita é prontamente convertida em um "programa de Wang" equivalente usando as instruções acima.
1974: Primeiro modelo de Davis Martin Davis era um estudante de graduação de Emil Post. Junto com Stephen Kleene, ele completou seu doutorado sob orientação de Alonzo Church (Davis (2000) 1ª e 2ª notas de rodapé, p. 188).
O seguinte modelo foi apresentado por ele numa série de palestras no Courant Institute na NYU (New York University) em 1973–1974. Este é o modelo a que Davis aplicou formalmente o nome "máquina de Post–Turing" com sua "linguagem de Post–Turing". Assume-se que as instruções são executadas sequencialmente (Davis 1974, p. 71): "Escreva 1 "Escreva B "Vá para A Se ler 1 "Vá para A Se ler B "Direita "Esquerda Note que não há "pare".
1978 Segundo modelo de Davis O modelo a seguir aparece como um ensaio What is a computation? (O que é computação?) em Steen, páginas 241–267. Por alguma razão, Davis renomeou seu modelo como "Máquina de Turing–Post".
Neste modelo, Davis atribui o número "1" a "marca/barra" de Post e "0" ao quadrados em branco. Citando Davis: "Nós agora estamos prontos para introduzir a linguagem de programação de Turing-Post. Nesta linguagem, há sete tipos de instruções: "Imprima 1 "Imprima 0 "Vá para Direita "Vá para Esquerda "Vá para a etapa i se 1 foi encontrado "Vá para a etapa i se 0 foi encontrado "Pare
"Um programa de Turing–Post é então uma lista de instruções, em que cada uma delas é de um destes 7 tipos. É claro que em um programa real, a letra i, numa etapa qualquer, seja o quinto ou sexto tipo, pode ser substituído por um número definido (inteiro positivo)." (Davis em Steen, p. 247).
Confusão surge quando não se percebe que uma fita em branco é, na verdade impressa com zeros — não há "em branco". A divisão de Post da instrução "GO TO" ("branch" ou "jump") em duas, cria um conjunto maior de instruções (mas mais fácil de utilizar)de sete ao invés das seis instruções de Post. Não se menciona que as instruções Imprima 1, Imprima 0, Vá para Direita e Vá para Esquerda implicam que, depois de sua execução, o computador deve ir para próxima etapa na sequência numérica. Não se usam modelos de instruções modernos como os de Erlang para a transcrição da máquina de pilhas SSD2 (Davis et al. (1994) p. 322).
1994 (2ª Edição) Modelo de Davis–Sigal–Weyuker do programa de Post–Turing
"Embora a formulação de Turing que apresentamos esteja mais próxima em espírito daquela dada originalmente por Emil Post, foi a análise da computação de Turing que fez esta formulação parecer tão apropriada. Esta linguagem tem desempenhado um papel fundamental na ciência da computação teórica." (Davis et al. (1994) p. 129)
Este modelo permite a impressão de múltiplos símbolos. O modelo permite o B (em branco) ao invés de S0. A fita é infinita em ambas as direções. A cabeça ou a fita se movimentam, mas suas definições de DIREITA e ESQUERDA sempre especifica o mesmo resultado em ambos os casos. (Turing utilizou a mesma convenção).
Imprima σ ;Substitui o símbolo lido por σ IF s GOTO L ;Se o símbolo lido é s então vá para a primeira instrução rotulada como L RIGHT ;Vá para a posição imediatamente à direita do símbolo lido atualmente LEFT ;Vá para a posição imediatamente à esquerda do símbolo lido atualmente
Note que apenas um tipo de "jump" – um GOTO condicional – é especificado; para um desvio incondicional de uma string, GOTO deve testar cada símbolo.
Este modelo reduz ao alfabeto binário {0,1} as versões apresentadas anteriormente, como mostrado aqui:
Imprima 0 = ERASE ;Substitua o símbolo lido por 0 = B = (em branco) Imprima 1 ;Substitua o símbolo lido por 1 IF 0 GOTO L ;Se o símbolo lido é 0 então vá para a primeira instrução rotulada como L IF 1 GOTO L ;Se o símbolo lido é 1 então vá para a primeira instrução rotulada como L RIGHT ;Vá para a posição imediatamente à direita do símbolo lido atualmente LEFT ;Vá para a posição imediatamente à esquerda do símbolo lido atualmente
Exemplos de máquinas de Post–Turing Atomização de quíntuplas de Turing em uma sequência de instruções de Post-Turing O seguinte método de "redução" (decomposição, atomização) – de uma 5-tupla de 2-símbolos de Turing a uma sequência de 2-símbolos de instruções de Post-Turing – pode ser encontrada em Minsky (1961). Ele afirma que essa redução de "um programa ... em uma sequência de instruções " segue a essência da B-máquina de Hao Wang (itálico no original, cf Minsky (1961) p. 439).
(A redução de Minsky, que ele chama de sub-rotina, resulta em 5, em vez de 7, instruções de Post-Turing. Ele não atomizou Wi0: "Write (Escreva) o símbolo Si0; vá para o novo estado Mi0", e Wi1: "Write (Escreva) o símbolo Si1; vá para o novo estado Mi1". O seguinte método permite atomizar Wi0 e Wi1; em todos os outros aspectos os métodos são idênticos.)
Esta redução de 5-tuplas de Turing em instruções de Post-Turing pode não resultar num programa de Post–Turing "eficiente", mas será fiel ao programa de Turing original.
No exemplo a seguir, cada 5-tupla de Turing do algoritmo do castor de 2-estados converte em: (i) um "jump" (goto, branch) condicional, seguido por (ii) 2 ações da fita para o caso "0" – Print ou Erase ou None (Nenhum), seguido de Esquerda ou Direita ou Nenhum, seguido por (iii) um "jump" incondicional para o caso "0" para sua próxima instrução (iv) 2 ações da fita para o caso "1" – Print ou Erase ou None (Nenhum), seguido de Esquerda ou Direita ou Nenhum, seguido por (v) um "jump" incondicional para o caso "1" para sua próxima instrução
para um total de 1 + 2 + 1 + 2 + 1 = 7 instruções por estado de Turing.
Por exemplo, o estado de Turing "A" do Algoritmo do castor de 2-estados, escrito como duas linhas de 5-tuplas, é: