1- Principe de base
En 1936, Alan Turing décrit dans un article une machine capable de traiter de l'information (constituée de plusieurs symboles) jetant les bases de l'informatique.
Les principaux éléments de sa machine sont :
- un ruban sur lequel est écrit les symboles dans des cases qui se suivent. Pour illustrer le principe de fonctionnement, nous retenons le 0 et le 1 dans les cases,
- un mécanisme qui permet de faire déplacer le ruban en avant ou en arrière,
- une tête lecture/écriture qui peut lire le contenu d'une case et écrire soit vide, soit 0, soit 1,
- un programme qui décrit le traitement de l'information à effectuer en fonction de plusieurs états et de ce que la tête de lecture/écriture a lu,
- un registre d'état qui permet de retenir l'état courant du programme.
2- Explication du fonctionnement de la machine de Turing
Voyons comment se déroule le fonctionnement.
Etape 1
Le début du programme est déclaré à l'état e1.
La ligne de code indique de lire la case : elle est vide, puis d'écrire dans la case vide, puis de décaler le ruban vers la gauche et de mémoriser l'état e2.
Cette première ligne de code a permis de placer sous la tête de lecture le premier bit à traiter.
Traitement du premier bit
Pour ce premier bit, il y a deux cas de figure : soit c'est un 0 soit c'est un 1.
Traitement du second bit
État de la machine une fois le programme fini
Vous pouvez vous aider du simulateur indiqué dans les ressources pour vous aider : faites le fonctionner en mode pas à pas !
3- Exercices
a- Inversion de bits amélioré
Voici le programme à faire fonctionner :
Il ressemble au programme précédent, mais plusieurs changements ont été faits.
Analysons l'utilité de chaque état :
b- Travailler les exercices du simulateur donné en ressource
Hors mis la détéction de palindromme, vous devez les avoir compris parfaitement.
Un conseil : faites chaque exercice sur papier, et vous valider le résultat en lançant le simulateur.