Lorsque le mathématicien Alan Turing a développé sa théorie, il a imaginé une machine comprenant :

• un ruban infini sur lequel sont inscrits des symboles,
• une tête de lecture qui peut lire ou écrire un symbole à la fois,
• une suite finie d’instructions qui changent le symbole courant et déplacent la tête de lecture.

À quoi sert cette machine ?

Elle décrit simplement le fonctionnement de tout ordinateur. Tout ce qui peut s’écrire comme une suite finie d’instructions, c’est-à-dire tout programme ou algorithme, peut donc être exécuté par cette machine. Avec un ensemble bien choisi d’instructions, une machine de Turing peut simuler n’importe quelle autre machine de Turing : c’est ce qu’on appelle une machine de Turing universelle.

À quoi ça ressemble ?

Une machine de Turing est d’abord une expérience de l’esprit. Néanmoins, rien n’empêche d’en construire une. C’est ce qu’a fait Mike Davey.

(Via Seweryn)