C’est le mathématicien Anglais Alan Turing qui a trouvé et énoncé les bases théoriques de toute machine dite universelle, capable d’accomplir une série de tâches qu’on lui indique et dont les actions qu’elle réalise dépendent de ce qu’elle a déjà accompli. Pour ce faire, Turing a notamment inventé la notion d’état (ou « étape »). Selon l’état dans laquelle elle se trouve, elle pourra exécuter des actions différentes face à une même situation. Ce principe simple est le principe de base de tout processeur donc de tout système programmable. Sans l’apport de Turing, il n’y aurait ni ordinateur ni téléphone portable ni tout autre dispositif contenant un processeur ! Le concept de machine de Turing est connu dans le monde entier et beaucoup d’algorithmes ont été trouvés depuis des décennies , notamment dans le domaine des mathématiques (calculs en binaire, recherche de PGCD et de PPCM entre deux nombres, suites numériques et bien d’autres).

Alan Turing a imaginé un ruban de longueur infinie contenant des cases soit vides soit contenant le chiffre 0 ou le chiffre 1. Cela représente les données lues et éventuellement modifiées par la machine. Cette machine peut exécuter le programme (= suite d’instructions) que l’utilisateur lui aura communiqué, en répétant les 4 étapes suivantes :