machine de Post

CALCUL
INFORMATIQUE

Modèle de calculateur développé par Emil-Leon Post, voisin de la machine de Turing . Ce modèle a été publié en 1936 sous le nom de "Formulation 1" et est parfois appelé machine de Post. D'autre part ses travaux ont amené au problème dit de correspondance de Post lié à la concatenation pour lequel il n'existe pas d'algorithme.