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.