Le concept de machine de Turing est posé par Alan Turing avant l’ordinateur. C’est un exercice de formalisation censé représenter une personne virtuelle exécutant une procédure bien définie, en changeant le contenu des cases d’un ruban infini, en choisissant ce contenu parmi un ensemble fini de symboles. D’autre part, à chaque étape de la procédure, la personne doit se placer dans un état particulier parmi un ensemble fini d’états. La procédure est formulée en termes d’étapes élémentaires du type : « si vous êtes dans l’état 42 et que le symbole contenu sur la case que vous regardez est « 0 », alors remplacer ce symbole par un « 1 », passer dans l’état 17, et regarder maintenant la case adjacente à droite ».