Entrez dans le monde des algorithmes avec cette machine de Turing qui fonctionne exactement comme l’a décrit le père de l’informatique, le célèbre Mathématicien Alan Turing.
Petite introduction sur la Machine de Turing
C’est le mathématicien Anglais Alan Turing qui a trouvé et énoncé les bases théoriques de toute machine dite universelle, capable d’accomplir une série de tâches qu’on lui indique et dont les actions qu’elle réalise dépendent de ce qu’elle a déjà accompli. Pour ce faire, Turing a notamment inventé la notion d’état (ou « étape »). Selon l’état dans laquelle elle se trouve, elle pourra exécuter des actions différentes face à une même situation. Ce principe simple est le principe de base de tout processeur donc de tout système programmable. Sans l’apport de Turing, il n’y aurait ni ordinateur ni téléphone portable ni tout autre dispositif contenant un processeur ! Le concept de machine de Turing est connu dans le monde entier et beaucoup d’algorithmes ont été trouvés depuis des décennies , notamment dans le domaine des mathématiques (calculs en binaire, recherche de PGCD et de PPCM entre deux nombres, suites numériques et bien d’autres).
Alan Turing a imaginé un ruban de longueur infinie contenant des cases soit vides soit contenant le chiffre 0 ou le chiffre 1. Cela représente les données lues et éventuellement modifiées par la machine. Cette machine peut exécuter le programme (= suite d’instructions) que l’utilisateur lui aura communiqué, en répétant les 4 étapes suivantes :
1: Lecture d'une case
2: Instruction en cours
3: Fin du programme?
4: Changement d'état
Puis, retour à l’étape 1 : il s’agit d’un traitement cyclique. Ce principe, imaginé par Alan Turing, est la base de l’informatique donc de tous les ordinateurs, smartphones, et tablettes actuels, ainsi que des cartes électroniques qui contrôlent et pilotent votre four à micro-onde ou votre lave vaisselle !
Tester un programme
Comment ça fonctionne ?
La machine est conçue pour agir selon les questions suivantes :
- Dans quel état suis-je en ce moment ?
- Quel symbole je viens de lire ?
- Quel symbole dois-je écrire ?
- Dans quelle direction dois-je me diriger ?
- Dans quel état dois-je passer ?