bien sùr
c'est la machine à calculer la plus puissante au monde
(et la plus lente aussi mais bon
)
Son principe est très simple, il y a :
- un bloc opérateur
- un ruban
- une tête de lecture et d'écriture
Une étape de calcul se passe ainsi :
- la machine entre dans l'étape avec un état bien défini
- la tête de lecture lit le signe sur le ruban
- le bloc opérateur regarde dans son algorithme la case correspondant au signe et à l'état de la machine. Dans cette "case" se trouvent un triple avec :
- un signe
- un état
- un déplacement
- la tête d'écriture écrit alors le nouveau signe sur le ruban
- le bloc opérateur déplace le ruban comme indiqué (d'une case à la fois vers la gauche ou vers la droite)
- la machine entre dans un nouvel état
On part donc d'un état initial et d'une suite de signe sur le ruban, on met en marche la machine et elle analyse les signe, change d'état, de signe ainsi de suite jusqu'à ce qu'elle se mette dans l'état final.
Et avec seulement ce mécanisme simple on peut venir à bout de tous les algorithmes résolvables:
Hypothèse fondamentale de Church-Turing :
Tout algorithme peut-être décrit part un schème fonctionnelle de Turing et être réalisé dans la machine de Turing correspondantes.
pour ceux qui le souhaitent j'ai mis au point un script python qui fait le travail d'une machine de Turing universelle, (pouvant résoudre tous les algorithmes). Je pourrais vous le passer si vous souhaitez en découvrir plus.
Et un bouquin très interessant à propos de l'informatique, et o๠l'on parle des machines de Turing, c'est le
New Turing Omnibus de A. K. DEWDNEY.