Máquina de Post-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).