Définitions

Cours/Algorithmie/Machine de Turing/Définitions

Une machine de Turing est une structure minimaliste permettant d'être exécutée pour réaliser son programme. Commençons par définir sa structure :

définition

Une machine de Turing est composée :

d'un ruban (supposé infini) constitué de cases contiguës pouvant chacune contenir soit le caractère 0 soit le caractère 1
d'un curseur qui est positionné sur une case du ruban (on suppose que le ruban est infini à gauche et à droite du curseur)
d'un ensemble fini $Q$ d'états possibles, contenant les deux états :
- l'état initial noté START
- l'état d'acceptation, noté STOP
d'un état courant $q \in Q$
d'une fonction de transition $\delta(q, r) = (\delta_e(q, r), \delta_c(q, r), \delta_d(q, r))$ dépendant de l'état $q$ de la machine et du caractère $r$ contenu dans la case du ruban pointée par le curseur. Cette fonction définie sur $Q \times \{0, 1\}$ permet de modifier :
- l'état de la machine : $\delta_e : Q \times \{0, 1\} \mapsto Q$
- le caractère de la case du ruban pointée par le curseur : $\delta_c : Q \times \{0, 1\} \mapsto \{0, 1\}$
- la position du curseur : $\delta_d : Q \times \{0, 1\} \mapsto \{\leftarrow, \rightarrow\}$

Une machine c'est donc un programme (la fonction de transition) qui agit à partir de données (le ruban et l'état interne de la machine). Une machine de Turing n'a d'intérêt que si elle est exécutée :

définition

L'exécution d'une machine de Turing se déroule comme suit :

initialisation :
1. le ruban est constitué uniquement 0
2. l'état courant de la machine est l'état initial START
étape :
1. on lit l'état courant $q$ de la machine
2. Si $q$ vaut l'état d'acceptation STOP on arrête l'exécution de la machine
3. on lit le caractère $r$ dans la case du ruban pointée par le curseur
4. on écrit le caractère $\delta_c(q, r)$ dans la case du ruban pointée par le curseur
5. on déplace le curseur d'une case à droite ou à gauche selon la valeur de $\delta_d(q, r)$ (à gauche si $\leftarrow$, à droite si $\rightarrow$)
6. on change l'état courant de la machine en $\delta_e(q, r)$
7. retour en 2.1

L'exécution d'une machine de Turing ne s'arrête pas forcément. Elle ne le fait que si elle atteint l'état STOP, ce qui peut ne jamais arriver.

Remarquez la minimalité du fonctionnement :

on ne peut déplacer la tête de lecture que d'une case vers la gauche ou vers la droite (il est impossible d'écrire où l'on veut dans la mémoire comme on peut le faire avec un ordinateur classique)
on ne peut écrire qu'un caractère à la fois (pas d'entier, de réel, rien que 0 ou 1)
pas de variables
pas de boucle while ni de saut
un unique test entre un état et une case du ruban

Et pourtant (nous le verrons), elle capte toutes les possibilités d'un algorithme.

Exemples

Rien de tel que d'exécuter quelques machines pour mieux comprendre le fonctionnement général.

Répétitions

Considérons la machine de Turing dont une fonction de transition partielle est la suivante :

$\delta(\text{START}, 0) = (\text{UN}, 1, \rightarrow)$
$\delta(\text{UN}, 0) = (\text{START}, 0, \rightarrow)$

Montrer que la fonction de transition partielle précédente est suffisante pour que l'exécution de la machine soit bien définie

solution

À l'initialisation le ruban est rempli de 0 et comme la machine ne va que à droite, le caractère lu sur le ruban ne peut être que 0. Comme l'état initial est START, la machine va osciller entre l'état START et UN.

Montrer que l'exécution de cette machine de Turing ne va jamais s'arrêter

solution

La fonction de transition ne contient pas de changement d'état vers STOP.

Que fait cette machine ?

solution

À chaque étape la machine écrit 1 (respectivement 0) si elle a précédemment écrit 0 (respectivement 1) et se déplace à droite

Voir une machine de Turing s'exécuter est très gratifiant, surtout lorsqu'on a passé du temps à la créer. Il existe de nombreux sites permettant de visualiser l'exécution d'une machine, nous allons utiliser celui-ci :

https://turingmachine.io/

Il utilise une définition plus générale d'une machine de Turing (c'est celle - classique - de Wikipedia) mais nous pouvons tout à fait utiliser notre définition.

Reprenons notre exemple et vérifions que nous avons bien compris son fonctionnement.

Copiez/coller le code ci-dessous dans la fenêtre de texte de la page https://turingmachine.io/ , puis cliquez sur le bouton load machine.

blank: 0
start state: START
table:
  START:
    0: {
      write: 1,
      R: UN
    }
  UN:
    0: {
      write: 0,
      R: START
    }
  STOP:

Le code de la machine de Turing utilisé est expliqué au bas de la page du site.

La machine est chargée :

chargement exemple

On y voit :

un diagramme représentant la fonction de transition (les état sont les sommets et les arcs les transitions)
le ruban et son curseur

Grâce aux boutons step et run sous le ruban, vous pourrez exécuter une étape de la machine ou en continue.

Exécutez plusieurs étapes de la Machine et vérifiez que les états sont bien représentez sur le diagramme au dessus de du ruban.

Jouons un peu avec cette machine :

Modifiez le code précédant pour que la machine écrive indéfiniment 110 sur le ruban.

solution

blank: 0
start state: START
table:
  START:
    0: {
      write: 1,
      R: UN
    }
  UN:
    0: {
      write: 1,
      R: DEUX
    }
  DEUX:
    0: {
      write: 0,
      R: START
    }

  STOP:

Modifiez le code précédant pour que la machine commence par écrire 110 sur le ruban, puis revienne en arrière sans modifier le ruban et s'arrête lorsque le curseur est de nouveau sur la position de départ.

répétition retour

solution

blank: 0
start state: START
table:
  START:
    0: {
      write: 1,
      R: UN
    }
    1: {
      write: 1,
      L: STOP
    }

  UN:
    0: {
      write: 1,
      R: DEUX
    }

  DEUX:
    0: {
      write: 0,
      L: START
    }

  STOP:

Oscillation

Considérons la machine de Turing dont une fonction de transition partielle est la suivante :

$\delta(\text{START}, 0) = (\text{L1}, 0, \leftarrow)$
$\delta(\text{L1}, 0) = (\text{R0}, 1, \rightarrow)$
$\delta(\text{R0}, 0) = (\text{R1}, 0, \rightarrow)$
$\delta(\text{R0}, 1) = (\text{R0}, 1, \rightarrow)$
$\delta(\text{R1}, 1) = (\text{R0}, 1, \rightarrow)$
$\delta(\text{R1}, 0) = (\text{STOP}, 1, \leftarrow)$

Montrer que la fonction de transition partielle précédente est suffisante pour que l'exécution de la machine soit bien définie

solution

Les transitions à partir des états R0 et R1 sont définis pour 0 et 1. Seul L1 n'est défini que pour 0. Or la seule étape où la machine peut se trouver dans l'état L1 est la seconde étape (les autres transitions ne transitionnent jamais vers L1), où il ne peut y avoir qu'un 0 sur la case du ruban pointée par le curseur.

Montrer que l'exécution de cette machine de Turing va s'arrêter et donnez les caractères présents sur le ruban

solution

···01010···

Écrivez le code de l'oscillateur.

solution

blank: 0
start state: START
table:
  START:
    0: {
      write: 0,
      L: L1
    }
  L1:
    0: {
      write: 1,
      R: R0
    }
  R0:
    0: {
      write: 0,
      R: R1
    }
    1: {
      write: 1,
      R: R0
    }
  R1:
    1: {
      write: 1,
      R: R0
    }
    0: {
      write: 1,
      L: STOP
    }
  STOP:

On va maintenant faire osciller l'oscillateur infiniment.

Que faudrait-il ajouter/modifier à la fonction de transition pour que la machine oscille infiniment ?

solution

$\delta(\text{START} = (\text{L1}, 0, \leftarrow)$
$\delta(\text{L1}, 0) = (\text{R0}, 1, \rightarrow)$
$\delta(\text{L1}, 1) = (\text{L0}, 1, \leftarrow)$ (Ajout)
$\delta(\text{R0}, 0) = (\text{R1}, 0, \rightarrow)$
$\delta(\text{R0}, 1) = (\text{R0}, 1, \rightarrow)$
$\delta(\text{R1}, 1) = (\text{R0}, 1, \rightarrow)$
$\delta(\text{R1}, 0) = (\text{L0}, 1, \leftarrow)$ (Modification)
$\delta(\text{L0}, 0) = (\text{L1}, 0, \leftarrow)$ (Ajout)
$\delta(\text{L0}, 1) = (\text{L0}, 1, \leftarrow)$ (Ajout)

Écrivez le code de l'oscillateur infini.

solution

blank: 0
start state: START
table:
  START:
    0: {
      write: 0,
      L: L1
    }
  L1:
    0: {
      write: 1,
      R: R0
    }
    1: {
      write: 1,
      L: L0
    }
  R0:
    0: {
      write: 0,
      R: R1
    }
    1: {
      write: 1,
      R: R0
    }
  R1:
    1: {
      write: 1,
      R: R0
    }
    0: {
      write: 1,
      L: L0
    }
  L0:
    0: {
      write: 0,
      L: L1
    }
    1: {
      write: 1,
      L: L0
    }

  STOP:

Sortie et Entrée d'une machine

Sortie

Mais si la machine s'arrête, le ruban constitue sa sortie. Comme la machine a effectuée un nombre fini d'étape avant de s'arrêter, on peut uniquement considérer une portion finie de celui-ci :

définition

La sortie d'une machine de Turing est constituée la partie finie du ruban entourant le curseur allant de :

la case contenant le caractère 1 le plus à gauche du curseur ou la case contenant le curseur s'il n'y a que des 0 à gauche du curseur
à la case contenant le caractère 1 le plus à droite la case contenant le curseur s'il n'y a que des 0 à droite du curseur

Par exemple si le ruban est :

···0110001101010000···
        ^

la sortie sera : 11000110101

Et si le ruban vaut :

···0110001101010000···
                ^

La sortie sera : 1100011010100

Cette définition de sortie n'est pas totalement satisfaisante puisqu'elle est vaut soit 0 soit elle aura un 1 au début ou à la fin. On peut régler ce problème en entourant toujours le ruban d'un 1 à gauche et d'un 1 à droite. Les sorties seront alors ainsi toutes les suites commençant et finissant pas un 1 ce qui n'est pas gênant il suffit de les supprimer a posteriori.

Entrée

Avant de définir l'entrée d'une machine de Turing, commençons par une propriété anodine mais avec de grosses conséquences :

définition

Si $M$ et $M'$ sont deux machines de Turing, on définit la machine de Turing $M+M'$ en suivant la procédure suivante :

on s'assure que les états de $M$ et les états de $M'$ (à part START et STOP) soient différents
on renomme l'état STOP de la machine $M$ en START'
on renomme l'état START de la machine M' en START'

La définition ci-dessus nous permet d'exécuter à la suite deux machine de Turing, l'état de fin de la première machine devenant l'état de départ de la suivante.

Notez que l'addition de Machine de Turing n'est pas commutative mais est associative.

Cette addition nous permet d'exécuter une machine $M$ avec autre chose que des 0 sur le ruban en exécutant la machine $M_\text{Init} + M$, avec $M_\text{Init}$ une machine qui prépare le ruban.

Par exemple, supposons que l'on veuille exécuter la machine oscillateur avec la chaîne 0101 sur le ruban on peut commencer par utiliser la machine de fonction de transition :

$\delta(\text{START}, 0) = (UN, 1, \rightarrow)$
$\delta(UN, 0) = (DEUX, 0, \rightarrow)$
$\delta(DEUX, 0) = (TROIS, 1, \leftarrow)$
$\delta(TROIS, 0) = (QUATRE, 0, \leftarrow)$
$\delta(QUATRE, 1) = (STOP, 1, \leftarrow)$

Qui laisse le ruban avec les données ···01010··· et le curseur sur le 0 le plus à gauche.

Codez la machine ci-dessus sur sur https://turingmachine.io/ et vérifiez son fonctionnement.

solution

blank: 0
start state: START
table:
  START:
    0: {
      write: 1,
      R: UN
    }
  UN:
    0: {
      write: 0,
      R: DEUX
    }
  DEUX:
    0: {
      write: 1,
      L: TROIS
    }
  TROIS:
    0: {
      write: 0,
      L: QUATRE
    }
  QUATRE:
    1: {
      write: 1,
      L: STOP
    }

  STOP:

On exécute ensuite, initialisation notre oscillateur.

Cette succession de l'exécution de deux machines est une machine dont la fonction de transition complète de cette nouvelle machine serait, en respectant les règle de l'addition :

$\delta(\text{START}, 0) = (UN, 1, \rightarrow)$
$\delta(UN, 0) = (DEUX, 0, \rightarrow)$
$\delta(DEUX, 0) = (TROIS, 1, \leftarrow)$
$\delta(TROIS, 0) = (QUATRE, 0, \leftarrow)$
$\delta(QUATRE, 1) = (START', 1, \leftarrow)$
$\delta(\text{START'}, 0) = (\text{L1}, 0, \leftarrow)$
$\delta(\text{L1}, 0) = (\text{R0}, 1, \rightarrow)$
$\delta(\text{R0}, 0) = (\text{R1}, 0, \rightarrow)$
$\delta(\text{R0}, 1) = (\text{R0}, 1, \rightarrow)$
$\delta(\text{R1}, 1) = (\text{R0}, 1, \rightarrow)$
$\delta(\text{R1}, 0) = (\text{STOP}, 1, \leftarrow)$

Combinez le code de la machine qui initialise et l'oscillateur pour tester le résultat sur https://turingmachine.io/

solution

blank: 0
start state: START
table:
  START:
    0: {
      write: 1,
      R: UN
    }
  UN:
    0: {
      write: 0,
      R: DEUX
    }
  DEUX:
    0: {
      write: 1,
      L: TROIS
    }
  TROIS:
    0: {
      write: 0,
      L: QUATRE
    }
  QUATRE:
    1: {
      write: 1,
      L: START'
    }
  START':
    0: {
      write: 0,
      L: L1
    }
  L1:
    0: {
      write: 1,
      R: R0
    }
  R0:
    0: {
      write: 0,
      R: R1
    }
    1: {
      write: 1,
      R: R0
    }
  R1:
    1: {
      write: 1,
      R: R0
    }
    0: {
      write: 1,
      L: STOP
    }
  STOP:

Ce cas étant très courant, plutôt que de concaténer une machine qui initialise le ruban à la machine principale, on donne la possibilité de donner une entrée à l'exécution d'une machine :

définition

Le paramètre d'entrée de l'exécution d'une machine de Turing $M$ est une suite finie $E$ (pouvant être vide) de caractères 0 et 1.

Lors de l'initialisation de l'exécution de la machine on rajoute deux étapes :

inscription de la chaîne E sur le ruban
positionnement du curseur sur la case contenant le premier élément de la chaîne.

L'exécution de la machine $M$ avec l'entrée $E$ s'écrit : $M(E)$

Remarquez bien que :

l'ajout d'un paramètre d'entrée n'est qu'une facilité d'écriture, cela ne change rien au modèle initial de la machine de Turing.
l'entrée est finie puisqu'elle résulte de l'exécution d'une machine. Il est donc impossible d'initialiser un ruban avec un nombre infini de 1.

En utilisant le code https://turingmachine.io/ de l'oscillateur infini, ajoutez la chaîne 01110111 comme paramètre d'entrée avec le mot clé input:

solution

blank: 0
start state: START
input: '0101'
table:
  START:
    0: {
      write: 0,
      L: L1
    }
  L1:
    0: {
      write: 1,
      R: R0
    }
    1: {
      write: 1,
      L: L0
    }
  R0:
    0: {
      write: 0,
      R: R1
    }
    1: {
      write: 1,
      R: R0
    }
  R1:
    1: {
      write: 1,
      R: R0
    }
    0: {
      write: 1,
      L: L0
    }
  L0:
    0: {
      write: 0,
      L: L1
    }
    1: {
      write: 1,
      L: L0
    }

  STOP:

Attention cependant, une machine peut s'arrêter pour certaines entrées et pas d'autres. On défini alors :

définition

Un machine de Turing $M$ accepte la chaîne de caractères $E\in \{0, 1\}^\star$ (qui peut être vide) si l'exécution de $M(E)$ s'arrête. Par abus de notation, on associera alors $M(E)$ à sa sortie.

Le langage de $M$ est l'ensemble de toutes les chaînes de caractères $E\in \{0, 1\}^\star$ qu'elle accepte.