MACHINE TURING

Quoique son nom de « machine » puisse conduire à croire le contraire, une machine de Turing est un concept abstrait, c’est-à-dire un objet mathématique. Une machine de Turing comporte les éléments suivants :

  1. un ruban infini divisé en cases consécutives. Chaque case contient un symbole parmi un alphabet fini. L’alphabet contient un symbole spécial appelé « symbole blanc » (‘0’ dans les exemples qui suivent), et un ou plusieurs autres symboles. Le ruban est supposé être de longueur infinie vers la gauche ou vers la droite, en d’autres termes la machine doit toujours avoir assez de longueur de ruban pour son exécution. On considère que les cases non encore écrites du ruban contiennent le symbole « blanc » ;
  2. une tête de lecture/écriture qui peut lire et écrire les symboles sur le ruban, et se déplacer vers la gauche ou vers la droite du ruban ;
  3. un registre d’état qui mémorise l’état courant de la machine de Turing. Le nombre d’états possibles est toujours fini, et il existe un état spécial appelé « état de départ » qui est l’état initial de la machine avant son exécution ;
  4. une table d’actions qui indique à la machine quel symbole écrire sur le ruban, comment déplacer la tête de lecture (par exemple « G » pour une case vers la gauche, « D » pour une case vers la droite), et quel est le nouvel état, en fonction du symbole lu sur le ruban et de l’état courant de la machine. Si aucune action n’existe pour une combinaison donnée d’un symbole lu et d’un état courant, la machine s’arrête.

[3d-flip-book mode= »fullscreen » urlparam= »fb3d-page » id= »216970″ title= »false »]

Turing_Machine : Vue d’artiste d’une machine de Turing ː un ruban infini muni d’une tête de lecture/écriture. La machine dispose également d’une table de transition, non représentée sur l’image.