Màquina de Post

En teoria de la computació i teoria de la recursión, una màquina de Post, batejada aixina en honor d'Emil Leon Post, és un autómata determinista en una coa. No hi ha cinta de llectura separada.

Al principi del còmput, la cadena d'entrada $x$ és carregada en la coa. La cadena d'entrada és seguida per un símbol especial de fin d'entrada. En iniciar-se el còmput, la coa solament conté la configuració d'entrada. El primer símbol de $x$ està al principi de la coa i el símbol de final d'entrada està després de l'últim caràcter. Una màquina de transició de Post depén del símbol al front de la coa i de l'estat. Cada transició borrarà el símbol al principi de la coa. Una transició té dos components: el pròxim estat i una cadena que s'inserta al final de la coa. La cadena pot ser buida.

Referències

• V. A. Uspenski, "A Post Machine" (rus), Moscou, "Naúka", 1979.