PRINCIPE

Définition

Bien que souvent associée à la machine créée lors de la seconde guerre mondiale, ‘Machine de Turing’ désigne en fait un concept mathématique abstrait imaginé par Alan Turing en 1936, alors que les ordinateurs n'existaient pas encore, afin de définir le concept d’algorithme ou de « procédure mécanique ». En effet, elle a la capacité de calculer tout ce problème mathématique calculable.

Fonctionnement

Une machine de turing est définie par les éléments suivants:


- Un ruban infini, divisé en cases consécutives,
- Une tête de lecture/écriture,
- Un registre d’état,
- Une table d’action.
Ainsi, chaque case du ruban contient une donnée, lisible et modifiable par la tête de lecture/écriture. En fonction de l’état dans lequel la machine se trouve, elle exécute les instructions dans la table d’action pour l’état donné.
Vous pouvez trouver un exemple de machine de Turing en vous interressant à notre jeu intéractif sur la page d'Acceuil! Sur cet exemple, le premier tableau représente le ruban infini (il y a une infinité de case vides avant et après), la case orange représente la tête de lecture et d'écriture, et on peux retrouver le registre d'état dans la table d'action en dessous.

Indice