Machines de Turing

Alan Turing (1912-1954).

Description informelle d’une MT

- une tête de lecture qui indique le caractère suivant à lire sur le ruban d’entré où est placé l’instance du problème ;

- un ensemble d’états finis (état initial et états accepteurs) ;

- une fonction de transition qui indique pour chaque état et chaque symbole lu l’état suivant, le symbole écrit et le sens de déplacement de la tête de lecture

Machines de Turing (suite)

Exécution informelle d’une MT

– Départ : état initial et tête de lecture sur le premier caractère du mot d’entrée ;

– A chaque étape :

1. lecture du caractère sous la tête de lecture ;

2. remplacement du caractère lu par celui de la fonction de transition ;

3. déplacement de la tête de lecture selon la fonction de transition ;

4. changement d’état selon la fonction de transition.

– Arrêt : Le mot est accepté si la MT atteint un état accepteur.

Description formelle d’une MT

def. Soit M = (Q, Γ, Σ, δ, s, #, F)

- Q est un ensemble fini d’états,

- Γ est un alphabet de ruban,

- Σ est un alphabet d’entrée,

- δ : ((Q × Γ) → (Q × Γ^{∗} × {g, d})) la fonction de transition,

- s ∈ Q l’état initial,

- # ∈ Γ − Σ le caractère “blanc”,

- F ⊆ Q l’ensemble des états accepteurs.

M est une machine de Turing.

exe.: Soit M_{1} = ( \begin{matrix}\{q_{0}, q_{1}, q_{2}, q_{3}, q_{4}\}, \{a, b, X, Y, #\}, \\ \{a, b\}, δ, q_{0}, #, \{q_{4}\}) \end{matrix}

avec δ : \{ \begin{matrix}((q_{0}, a)(q_{1}, X, d)), ((q_{0}, Y), (q_{3}, Y, d)), \\ ((q_{1}, a), (q_{1}, a, d)), ((q_{1}, b), (q_{2}, Y, g)), \\ ((q_{1}, Y), (q_{1}, Y, d)), ((q_{2}, a), (q_{2}, a, g)), \\ ((q_{2}, X), (q_{0}, X, d)), ((q_{2}, Y), (q_{2}, Y, g)), \\ ((q_{3}, Y), (q_{3}, Y, d)), ((q_{3}, #), (q_{4}, #, d))\}. \end{matrix}

M_{1} est une machine de Turing.

Description formelle d’une MT

(suite)

def.: Le triplet (q, α, β) ∈ (Q × Γ^{∗} × (ε ∪ Γ^{∗}(Γ − {#}))) est une configuration avec :

- q l’état de la machine,

- α le mot apparaissant avant la tête de lecture,

- β le mot apparaissant entre la position de la tête de lecture (incluse) et le dernier caractère non blanc.

def.: De la configuration (q, α, β), les configurations suivantes sont dérivables en une étape par la machine de Turing M (β = bβ′ avec b = # si β = ε)

- si δ(q, b) = (q′, b′, d) alors (q, α, β) ⊢_{M} (q′, αb′, β′) ;

- si δ(q, b) = (q′, b′, g) et α = α′a alors (q, α, β) ⊢_{M} (q′, α′, ab′β′).

Remarque : Lors d’un déplacement à gauche (g) α ≠ ε donc il existe α′ ∈ Γ^{∗} et a ∈ Γ tels que α = α′a.

Description formelle d’une MT

(suite)

def.: Une configuration C′ est dérivable en plusieurs étapes de la configuration C par la machine de Turing M (C ⊢_{M}^{∗} C′) si ∃k ≥ 0 et C_{0}, …, C_{k} des configurations telles que

- C = C_{0},

- C′ = C_{k},

- C_{i} ⊢_{M} C_{i+1} , ∀i, 0 ≤ i < k.

exo.: Montrer que la machine de Turing M_{1} dérive (en plusieurs étapes) la configuration (q_{4}, XXY Y #, ε) de (q_{0}, ε, aabb).

def.: Un mot est accepté par une machine de Turing M si (s, ε, w) ⊢_{M}^{∗} (q, α, β) avec q ∈ F.

def.: Un langage est récursivement énumérable si il est accepté par une machine de Turing.

Exécution d’une MT

def.: L’exécution d’une machine de Turing M sur un mot w est la suite maximale (possiblement infinie) des configurations (s, ε, w) ⊢_{M} (q_{1}, α_{1}, β_{1}) ⊢_{M} … ⊢_{M} (q_{n}, α_{n}, β_{n}) ⊢_{M} . . ..

Cette suite est

- soit finie (se terminant en une configuration dont l’état est accepteur ou à partir de laquelle il n’y a pas de transition possible),

- soit infinie.

def.: Un langage L est décidé par une machine de Turing M si

- M accepte L,

- M n’a pas d’exécution infinie.

def. Un langage est récursif si il est décidé par une machine de Turing.