loader

drive02

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 :

fancybox

1: Lecture d'une case

La machine lit la valeur de la case en cours de traitement.
fancybox

2: Instruction en cours

En fonction de la valeur de la case lue et de l'état (= numéro) de la machine et de l'instruction en cours à exécuter, la machine modifie ou ne modifie pas le contenu de cette case (exemple : la machine est dans l'état 5, elle vient de lire 1, dans ce cas, elle doit remplacer le 1 par un 0, comme lui dicte l'instruction en cours) ;
fancybox

3: Fin du programme?

Soit la machine s'arrête (fin du programme), soit elle continue en pointant la case à droite ou à gauche de celle qu'elle vient de traiter ;
fancybox

4: Changement d'état

La machine change éventuellement d'état, si le code du programme utilisateur lui impose de le faire.

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 ?
drive02

Essayez nos algorithmes !

10 exemples d'algorithmes prêts à être codé