Normalisation

Résultat

Le but de cette partie est de montrer qu'on peut toujours supposer qu'une machine de Turing possède deux états spéciaux q₊ et q_- tels que

• q₊ est final (q₊ ∈ F) et q_- n'est pas final (q_- ∉ F),
• la machine se bloque dès qu'elle est dans un des états q₊ ou q_-,
• la machine se bloque uniquement dans un des états q₊ ou q_-.

Pour montrer ce résultat, nous allons montrer qu'à partir d'une machine M, on peut toujours construire une autre machine de Turing M' qui accepte les mêmes entrées que M et qui vérifie les propriétés ci-dessus. Nous allons montrer en outre que si la machine M est déterministe alors la machine M' est aussi déterministe.

Analyse

Une machine de Turing peut se bloquer dans un état q pour deux raisons.

1. La première raison est qu'aucune transition n'est possible. Supposons que machine est dans état p et que le symbole de bande sous la tête est le symbole a. Si la machine n'a pas de transition de la forme p, a → q, b, x pour x ∈ {L, R}, alors elle reste bloquée en p.
2. La seconde raison est que certaines transitions sont possibles mais que ces transitions conduisent à un déplacement de la tête de lecture vers la gauche alors que cette tête est justement sur la première position de la bande. Supposons que machine est dans état p, que la tête de lecture est sur la première position de la bande et que le symbole de bande sous cette tête est le symbole a. Si la machine a des transitions de la forme p, a → q, b, L mais pas de transitions de la forme p, a → q, b, R, alors elle reste bloquée en p. En effet, la définition des machines de Turing stipule qu'une machine n'a pas le droit d'effectuer une transition qui déplace la tête de lecture vers la gauche lorsque cette tête de lecture est justement sur la première position de la bande.

Idées générales de la construction

L'idée générale de la construction de M' est d'ajouter deux nouveaux états q₊ et q_- à M et d'ajouter les transitions pour que la machine M' passe dans un de ce deux états quand la machine M se bloque dans un état p. Le premier type de blocage est facile à détecter dans la machine M. Il suffit de trouver toutes les paires (p, a) telle qu'il n'existe pas de transition p, a → q, b, L pour x ∈ {L, R}. Le second type de blocage est plus délicat à détecter puisque la machine M' doit savoir quand sa tête de lecture se trouve sur la première position de la bande. Pour contourner cette difficulté, on ajoute de nouveaux symboles de bandes à la machine M'. Pour chaque symbole de bande a de M, la machine M' contient le symbole a et un autre symbole correspondant a. L'alphabet de bande M' est donc Γ' = Γ ∪ { a | a ∈ Γ }. Ces nouveaux symboles seront uniquement utilisés dans la première position de la bande et serviront à la machine pour détecter cette position. L'alphabet d'entrée de M' est identique à celui de M. La première opération de la machine M' est de remplacer le premier symbole a de l'entrée par le symbole a correspondant pour marquer la première position de la bande. À cette fin, on ajoute deux nouveaux états q'₀ et q'₁ et quelques transitions. Ensuite toutes les autres transitions de M' remplacent un caractère non souligné a par un caractère non souligné b et un caractère souligné a par un caractère souligné b. Ainsi, la première position de la bande contient toujours un symbole souligné et toutes toutes les autres positions contiennent des symboles non soulignés.

La construction proprement dite

Soit M = (Q, Σ, Γ, E, q₀, F, #) une machine de Turing. Nous décrivons la machine de M' qui accepte les même entrées mais qui se bloque uniquement dans un des deux états q₊ ou q_-. Par rapport à la machine M, la machine M' possède quatre nouveaux états qui sont les états q'₀, q'₁, q₊ et q_-.

• États : Q'= Q ∪ {q'₀, q'₁, q₊, q_-}
• État initial : q'₀
• États finaux : F' = { q₊ }
• Alphabet de bande : Γ' = Γ ∪ { a | a ∈ Γ }
• Alphabet d'entrée : Σ' = Σ
• Caractère blanc : #

Il reste à décrire l'ensemble E' des transitions de M'. Cet ensemble est décomposé en E' = E₀ ∪ E₁ ∪ E₂ ∪ E₃ ∪ E₄ suivant l'état p dans lequel se trouve la machine. Les ensembles E₀, E₁, E₂, E₃ et E₄ sont définis ci-dessous.

p = q'₀

La première transition est chargée de remplacer le premier caractère de l'entrée par le caractère souligné correspondant.

E₀ = { q'₀, a → q'₁, a, R | a ∈ Γ }.

p = q'₁

La seconde transition est chargée de remettre la tête de lecture sur la première position de la bande et de passer dans l'ancien état final q₀ pour commencer le calcul.

E₁ = { q'₁, a → q₀, a, L | a ∈ Γ }.

p = q₊ ou p = q_-

Pour que la machine M' se bloque en q₊ et en q_- elle ne possède aucune transition de la forme q₊, a → q, b, x et aucune transition de la forme q_-, a → q, b, x pour x ∈ {L, R}.

p ∈ Q

On commence par ajouter à M' toutes les transitions de M pour les lettres non soulignées et les lettres soulignées. On pose

E₂ = { p, a → q, b, x | p, a → q, b, x ∈ E } ∪ { p, a → q, b, R | p, a → q, b, R ∈ E }

Ensuite, on ajoute des transitions spécifiques pour éviter que M' ne se bloque dans des états autres que q₊ et q_-. On pose U l'ensemble des paires (p,a) telles que M ne possède pas de transitions p, a → q, b, x pour x ∈ {L, R} et V l'ensemble des paires (p,a) telles que M ne possède pas de transitions p, a → q, b, R. On définit alors les deux ensembles E₃ et E₄.

E₃ = { p, a → q₊ a, R | si (p, a) ∈ U et p ∈ F } ∪ { p, a → q_- a, R | si (p, a) ∈ U et p ∉ F }.
E₄ = { p, a → q₊ a, R | si (p, a) ∈ V et p ∈ F } ∪ { p,a → q_- a, R | si (p, a) ∈ V et p ∉ F }.

Il est facile de vérifier que si la machine M est déterministe, alors la machine M' est également déterministe.

Exemple