Máquina de Post-Turing

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 O_i [O_i = (a), (b), (c) ou (d)] e então siga a direção j_i,

(B) Execute a operação (e) e de acordo com a resposta sim ou não correspondente, siga a direção j_i' ou j_i' ' ,

(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):

q_i S_j L q_l,

q_i S_j R q_l,

q_i S_j S_k q_l

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 S₀. 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, é:

m-Configuração Inicial (Estado de Turing)	Símbolo da fita	Operação de impressão	Movimento de fita	m-Configuração Final (Estado de Turing)
A	0	P	R	B
A	1	P	L	B

A tabela representa apenas uma única instrução de Turing, mas nós vemos que ela consiste de 2 linhas de 5-tuplas, uma para o caso "símbolo de fita sob a cabeça = 1", a outra para o caso "símbolo de fita sob a cabeça = 0". Turing observou (Undecidable, p. 119) que as colunas mais a esquerda – "m-configuração" e "símbolo" – representam a configuração atual da máquina - seu estado incluindo tanto a fita como a tabela naquele instante – e as três últimas colunas são seu comportamento subsequente. Como a máquina não pode estar em dois estados de uma só vez, a máquina deve "desviar para uma configuração ou para outra:

m-Configuração inicial e símbolo S	Operação de impressão	Movimento de fita	m-Configuração final
S=0 -->	P -->	R -->	B
--> A <
S=1 -->	P -->	L -->	B

Depois da configuração de desvio (J1 xxx) ou (J0 xxx), a máquina segue um dos dois comportamentos subsequentes. Nós listamos estes dois comportamentos em uma linha, e os numeramos (ou rotulamos) sequencialmente(exclusivamente). Abaixo de cada desvio (branch, go to), nós colocamos seu desvio para o "número" (endereço, localização):

	m-Configuração inicial & símbolo S	Operação de impressão	Movimento de fita	m-Configuração final, caso S=0	Operação de impressão	Movimento de fita	m-Configuração final, caso S=1
	If S=0 then:	P	R	B
	---> A <
	If S=1 then:				P	L	B
instrução #	1	2	3	4	5	6	7
Instrução de Post–Turing	J1	P	R	J	P	L	J
jump-to (desvie para) instrução #	5			B			B

De acordo com as convenções da máquina de Post–Turing cada uma das instruções (Print, Erase, Left e Right) consiste de duas ações:

(i) Ação da fita: { P, E, L, R}, então

(ii) Ação da tabela: vá para a próxima instrução em sequência

E de acordo com as convenções da máquina de Post–Turing, os desvios condicionais ou "jumps" J0xxx, J1xxx consistem de duas ações:

(i) Ação da fita: Olha o símbolo sob a cabeça da fita

(ii) Ação da tabela: If símbolo é 0 (1) and J0 (J1) then goto xxx else goto próxima instrução na sequência

E de acordo com as convenções da máquina de Post–Turing, os desvios incondicionais ou "jump" Jxxx consistem de uma única ação, ou se nós quisermos, regularizamos a sequência de duas ações:

(i) Ação da fita: Olha o símbolo sob a cabeça da fita

(ii) Ação da tabela: If símbolo é 0 then goto xxx else if símbolo é 1 then goto xxx.

Quais e quantos desvios são necessários? O desvio incondicional Jxxx é simplesmente J0 seguido imediatamente por J1 (ou vice versa). Wang (1957) também demonstra que apenas um desvio condicional é necessário, isto é, ou J0xxx ou J1xxx. Contudo, com essa restrição a máquina torna díficil escrever instruções para este fim. Frequentemente, somente duas são usadas, isto é:

(i) { J0xxx, J1xxx }

(ii) { J1xxx, Jxxx }

(iii) { J0xxx, Jxxx },

mas o uso de todas as três { J0xxx, J1xxx, Jxxx } elimina instruções extras. No exemplo do algoritmo do castor de 2-estados, nós usamos somente { J1xxx, Jxxx }.

Algoritmo do Castor de 2-estados

A missão do algoritmo do Castor é imprimir o quanto for possível antes de parar. A instrução "Print" (Imprima) escreve um 1, o "Erase" (Apague) (não usado neste exemplo) escreve um 0 (isto é, o mesmo que P0). A fita move-se para a esquerda ou direita (isto é, a cabeça é estacionária).

Tabela de estados para o algoritmo do castor de máquina de Turing de 2-estados:

	Estado atual A:			Estado atual B:
	Símbolo escrito:	Movimento da fita:	Próximo estado:	Símbolo escrito:	Movimento da fita:	Próximo estado:
Símbolo da fita é 0:	1	R	B	1	L	A
Símbolo da fita é is 1:	1	L	B	1	N	H

Instruções para a versão de Post-Turing do algoritmo do castor de 2-estados: Observe que todas as instruções estão na mesma linha e em sequência. Este é um ponto significativo da versão de Turing e ela está no mesmo formato do que se chama "programa de computador":

Instrução #:	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Instrução:	J1	P	R	J	P	L	J	J1	P	L	J	P	N	J	H
Jump-to # (desvie para):	5			8			8	12			1			15
Rótulo do estado da máquina de Turing:	A							B							H

Alternativamente, nós podemos escrever a tabela como uma string. O uso de "separadores" de parâmatro ":" e separadores de instruções "," é algo de nossa escolha e não deve aparecer no modelo. Não há convenções (mas veja Booth (1967) p. 374, e Boolos & Jeffrey (1974, 1999) p. 23), para algumas idéias úteis de como combinar convenções de diagramas de estados com as instruções – ou seja, como usar as setas para indicar o destino dos desvios). No exemplo imediatamente abaixo, as instruções são sequenciais, começando de "1", e os parâmetros/operandos são considerados parte de suas instruções/"opcodes":

J1:5, P, R, J:8, P, L, J:8, J1:12, P, L, J1:1, P, N, J:15, H

O diagrama de estados de um Algoritmo do Castor de 2-estados (o pequeno desenho, no canto direito da figura) converte a máquina de Post-Turing equivalente com substituição de 7 instruções de Post-Turing pelos estados de "Turing". A instrução HALT (pare) adiciona o 15º estado:

Uma "caminhada" do algoritmo do castor de 2-estados com todos os passos intermediários das máquina de Post-Turing:

Algoritmo do castor de dois estados seguido de "limpeza da fita"

O seguinte exemplo é uma máquina de estados para a versão de Turing do algoritmo do castor de 2-estados com instruções adicionais (15-20) para demonstrar o uso de "Erase", J0, etc. Estas irão apagar os 1's escritos pelo algoritmo do castor:

Instrução #:	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
Instrução:	J1	P	R	J	P	L	J	J1	P	L	J	P	N	J	L	J0	E	R	J1	H
Jump-to (Desvie para) #:	5			8			8	12			1			15		20			17
Rótulo da máquina de estados de Turing:	A							B							*

As instruções adicionais de Post-Turing, de 15 a 20, apagam os símbolos criados pelo algoritmos do castor. Essas instruções "atômicas" são mais "eficientes" que sua equivalente máquina de estados de Turing (das 7 instruções Post–Turing). Para realizar a mesma tarefa, uma máquina de Post-Turing (geralmente) irá requerer menos estados de Post-Turing que uma máquina de Turing, porque (i) um desvio (go-to) pode ocorrer para qualquer instrução Post–Turing (por exemplo, P, E, L, R) dentro da máquina de estados de Turing, (ii) um agrupamente de instruções para movimentação da fita tal como L, L, L, P são possíveis, etc.:

Instrução #:	16	17	18	19	20
Instrução:	J0	E	R	J1	H
Jump-to (desvie para) #:	20			17

Exemplo: Multiplicação 3 × 4 com a máquina de Post–Turing

Um exemplo de "multiplicação" a × b = c na máquina de Post–Turing. No início, a fita (mostrada à esquerda) tem dois números nela – a' = 3' (4 marcações), b' = 4' (5 marcações). (Uma única marcação representaria "0".) Ao final, a fita terá o produto c' = 12' (13 marcações) à direita de b. Note que "top" e "bottom" estão lá apenas para esclarecer que a máquina de Post-Turing está trabalhando.

Este exemplo é uma referência para mostrar como a computação de uma multiplicação prosseguiria numa fita única, com 2 símbolos { blank (em branco), 1 } no modelo da máquina de Post–Turing.

Este algoritmo de multiplicação é recursivo através de dois loops. A cabeça se movimenta. Ela começa à extrema esquerda (o top) da string de marcações unárias representando a' :

• Mova a cabeça para a extremidade direita. Estabeleça (ou seja, "clear") o registro c colocando um único espaço em branco e então marque a direita de b
• a_loop: Mova a cabeça para a direita uma só voz, teste para a parte inferior de a' (um em branco). If "em branco", then done else apague a marcação;
• Mova a cabeça para a direita de b' . Mova a cabeça para direita uma única vez, passado a marca no topo de b' ;
• b_loop: If cabeça da fita está na parte inferior de b' (um "em branco") then mova a cabeça para extremidade esquerda de a' , else:

• Apague a marcação para localizar um contador (em branco) em b' .
• Incremente c' : Mova a cabeça da fita à direita do topo de c' e incremente c' .
• Mova a cabeça à esquerda do contador dentro de b' ,
• Repare o contador: imprima uma marcação no contador em branco.
• Decremente b' −count: Mova a cabeça para a direita uma única vez.
• Retorne ao b_loop.

Multiplicação a × b = c, por exemplo: 3 × 4 = 12. O local escaneado é indicado por colchetes ao redor da marcação, ou seja, [ | ]. Um marcador extra serve para indicar o símbolo "0":

No início da computação, a' é formado por 4 marcadores unários, então um espaço em branco separador b' é formado por 5 marcadores unários, em seguida um separador é marcado. Um número ilimitado de espaços vazios deve estar disponível para c à direita:

....a'.b'.... = : ....[ | ] | | | . | | | | | ....

Durante a computação, a cabeça vai e volta de a' para b' e para c' , volta para b' então para c' , então volta para b' , e vai para c' ad nauseam (argumento por repetição), enquanto a máquina conta através de b' e incrementos de c' . Multiplicação de a' está em contagem regressiva lenta (suas marcas apagadas – mostrado como referências com os x's abaixo). Um contador dentro de b' move para a direita através de b (uma marca apagada mostra que está sendo lido pela cabeça como [ . ] ) mas é reconstruído depois de cada passagem enquanto a cabeça retorna do incremento em c' :

....a.b.... = : ....xxx | . | | [ . ] | | . | | | | | | | ...

Ao fim da computação: c' está com 13 marcações = "sucessor de 12" aparecendo a direita de b' . a' desapareceu no processo da computação

....b.c = ......... | | | | | . | | | | | | | | | | | | | ...

Rodapés

^ a: Diferenças entre modelos da máquina de Turing e de Post–Turing

Em seu capítulo XIII Computable Functions (Funções computáveis), Kleene adota o modelo de Post; o modelo de Kleene utiliza um "em branco" e um símbolo "tally mark ¤" (Kleene p. 358), um "tratamento mais próximo em alguns aspectos a Post, 1936. Post (1936) considerou a computação com uma fita bidirecional infinita e somente 1 símbolo" (Kleene p. 361). Kleene observa que o tratamento de Post proporcionou uma redução maior a ações atômicas (Kleene p. 357) de "ações de Turing" (Kleene p. 379). Como descrito por Kleene "The Turing act" é uma combinação de 3 (tempo-sequencial) ações específicas em uma linha na tabela de Turing: (i) símbolo de "print"/erase/do-nothing (não faça nada) seguido por (ii) mova a fita para esquerda/mova a fita para direita/do-nothing (não faça nada) seguido por (iii) teste-fita segue (goto) próxima instrução: por exemplo, "s1Rq1" significa "Print symbol "¤" (Imprima o símbolo), então mova a fita para direita, então, se o símbolo da fita é "¤" vá para o estado q1". (Veja o exemplo de Kleene, P. 358).

Kleene observa que Post atomizou essas 3 ações em dois tipos de 2 ações. A primeira fita é uma ação de "print/erase", a segunda é uma ação de "mova a fita para esquera/direita": (1.i) Símbolo de impressão/erase/do-nothing seguido por (1.ii) teste- leve a fita para a próxima instrução, ou (2.ii) mova a fita para esquerda/mova a fita para direita/do-nothing seguida por (2.ii) teste- leve a fita para a próxima instrução.

Mas Kleene observa que enquanto

"Na verdade, pode-seargumentar que a ação da máquina de Turing já está composta, e consiste psicologicamente em uma impressão e uma mudança no "estado de espírito", seguido por um movimento e outro estado de espírito [, e] Post (1947) assim separou o ato de Turing em dois; nós não temos aqui, principalmente por ele guarda espaço nas tabelas da máquina não para fazê-lo."(Kleene p. 379)

De fato, o tratamento de Post (1936) é ambíguo; ambos (1.1) e (2.1) podem ser seguidos por "(.ii) vá para a próxima instrução na sequência". Isto significa uma maior atomização em três tipos de instruções: (1) print-símbolo de impressão/erase/do-nothing, então vá para próxima instrução da sequência numérica, (2) mova a fita para esquerda/mova a fita para direita/do-nothing(não faça nada), então vá para a próxima instrução na sequência, (3)teste a fita, então vá para instrução xxx, senão, vá para a próxima instrução na sequência.

Referências

• Stephen C. Kleene, Introduction to Meta-Mathematics, North-Holland Publishing Company, New York, 10th edition 1991, first published 1952. Chapter XIII is an excellent description of Turing machines; Kleene uses a Post-like model in his description and admits the Turing model could be further atomized, see Footnote 1.
• Martin Davis, editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. Papers include those by Gödel, Church, Rosser, Kleene, and Post.
• Martin Davis, "What is a computation", in Mathematics Today, Lynn Arthur Steen, Vintage Books (Random House), 1980. A wonderful little paper, perhaps the best ever written about Turing Machines. Davis reduces the Turing Machine to a far-simpler model based on Post's model of a computation. Includes a little biography of Emil Post.
• Martin Davis, Computability: with Notes by Barry Jacobs, Courant Institute of Mathematical Sciences, New York University, 1974.
• Martin Davis, Ron Sigal, Elaine J. Weyuker, (1994) Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science – 2nd edition, Academic Press: Harcourt, Brace & Company, San Diego, 1994 ISBN 0-12-206382-1 (First edition, 1983).
• Fred Hennie, Introduction to Computability, Addison–Wesley, 1977.
• Marvin Minsky, (1961), Recursive Unsolvability of Post's problem of 'Tag' and other Topics in Theory of Turing Machines, Annals of Mathematics, Vol. 74, No. 3, November, 1961.
• Roger Penrose, The Emperor's New Mind: Concerning computers, Minds and the Laws of Physics, Oxford University Press, Oxford England, 1990 (with corrections). Cf: Chapter 2, "Algorithms and Turing Machines". An overly-complicated presentation (see Davis's paper for a better model), but a thorough presentation of Turing machines and the halting problem, and Church's lambda calculus.
• Hao Wang (1957): "A variant to Turing's theory of computing machines", Journal of the Association for Computing Machinery (JACM) 4, 63–92.