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)
francbelge 
Hey, mais c’est trop la classe comme truc, un peu geek, mais super sympa. Merci pour cet article sur le génie Turing !
J’aimeJ’aime
« Néanmoins, rien n’empêche d’en construire une. »
Euh, le ruban infini peut-être? 😉
Ah non, attends, je viens d’en trouver un au fond de la poche de mon jean. J’ai rien dit.
Puis je sors.
J’aimeJ’aime
Ha ha ha 😀 Le ruban est théoriquement infini mais la machine peut très bien s’arrêter en temps fini, hein. :-p
J’aimeJ’aime