Une machine de Turing, c'est un ordinateur théorique . C'est en fait le modèle le plus simple (avec le lambda-calcul) d'un calculateur universel.

Universel, cela signifie que la machine de Turing peut, théoriquement, reproduire tous les calculs imaginables par un être humain, et "émuler" tous les ordinateurs existants ou à venir. Turing a en effet démontré, grâce à sa machine, que tous les ordinateurs se valent :  leurs possibilités de calcul sont les mêmes, même si leur rapidité diffère. Mais si l'on sait programmer un algorithme sur un ordinateur quelconque, dans n'importe quel langage informatique, alors il existe un programme équivalent pour la machine de Turing, et ce programme (même s'il est très lent) fournira le même résultat.

Il est intéressant de savoir que Turing a démontré cela dès 1940, à une époque ou les ordinateurs n'existaient pas !

J'ai inventé un raffinement supplémentaire à la machine de Turing...