Machine de Turing
À presque rien de matériel. C'est un objet de pensée : un ruban infini divisé en cases, une tête qui lit et écrit un symbole à la fois, et une table de règles. Turing l'a imaginée en 1936 pour définir ce qu'un calcul peut être.
À presque rien de matériel. C'est un objet de pensée : un ruban infini divisé en cases, une tête qui lit et écrit un symbole à la fois, et une table de règles. Turing l'a imaginée en 1936 pour définir ce qu'un calcul peut être.
Parce qu'elle définit le calculable. Turing montre qu'un même modèle très simple peut, en principe, effectuer n'importe quel calcul mécanique. Tout ordinateur d'aujourd'hui n'est, au fond, qu'une réalisation concrète de cette idée abstraite.
Qu'il existe des problèmes qu'aucun programme ne peut résoudre. Turing démontre en 1936 que rien ne peut décider, à coup sûr, si un programme quelconque finira par s'arrêter. Certaines questions sont donc, par nature, hors de portée de toute machine.