La machine de Turing : du concept à la réalisation

Alan Turing a décrit, dans une publication de 1936, un concept d’une extrême simplicité mais fondateur dans le domaine de l’informatique : la machine de Turing. Son article avait pour objectif de modéliser rigoureusement la notion d’algorithme, et d’apporter une réponse négative au problème de la décision en logique du premier ordre, formulé en 1928 par David Hilbert et Wilhelm Ackermann. Ce modèle abstrait, conçu comme une machine universelle, est capable - en théorie - d’exécuter toute opération qu’un ordinateur moderne peut réaliser.