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)
