Qu’est-ce que la calculabilité?

– Syndrome du “mouvement perpétuel”.

– Les limites intrinsèques de l’informatique.

– Quels problèmes sont solubles par un programme exécuté sur un ordinateur.

La notion de problème

Caractéristiques de la notion de problèmes : – générique,

– les instances du problème ont une réponses,

– le problème est indépendant de la manière de le ré-

soudre. Exemples de problèmes :

– Trier un tableau ;

– Déterminer si un programme termine quelque soit les données ;

– Déterminer si un polynôme à coefficients entiers a des racines entières.

La notion de programme

procédure effective: solution à un problème qui à la forme d’un programme pouvant être exécuté sur un ordinateur.

Solution au problème de l’arrêt : déterminer si le programme n’a pas de boucles ou de séquences d’appels récursifs infinies.

function mystere (n: entier) : entier begin

if (n = 1)

then 1

else if (pair n) then mystere(n/2) else mystere(3*n+1)

end;

Programme = automate

Représentation des problèmes

Nécessité d’une fonction d’encodage. def.: Un alphabet est un ensemble fini de symboles. def.: Un mot est une séquence finie de symboles (ε est le mot vide). Soit un problème encodé sur un alphabet. L’ensemble des mots est partitionné en deux :

– instances positives : la réponse est oui pour ce mot,

– instances négatives : ce mot n’encode pas un problème ou la réponse est non pour ce mot.

Représentation et langages

Un problème est caractérisé par l’ensemble des mots qui sont ses instances positives. def.: Un langage est un ensemble de mots définis sur le même alphabet. Équivalence entre résoudre un problème et reconnaître le langage des encodages des instances positives du problème. Th.: L’ensemble des sous-ensembles d’un ensemble dénombrable n’est pas dénombrable. Cor.: L’ensemble des langages n’est pas dénombrable.

Langage régulier

L’ensemble R des langages réguliers (ou rationnels) sur un alphabet Σ est le plus petit ensemble satisfaisant :

- ∅ ∈ R, {ε} ∈ R

- {a} ∈ R, ∀a ∈ Σ

- si A, B ∈ R alors A ∪ B, A · B, A^{∗} ∈ R.

Exemple : Les langages {a}^{∗} · ({a} ∪ {b}^{∗})({b}^{∗})^{∗} et {a}^{∗} · {b}^{∗} sont des langages réguliers (égaux !).

Les expressions régulières pour un alphabet Σ sont les expressions formées par les règles suivantes :

- ∅, ε et tous les éléments de Σ sont des expressions régulières.

- si α et β sont des expressions régulières alors (αβ), (α + β), et (α)^{∗} sont des expressions régulières.

Exemple : Les expressions a^{∗}(a + b^{∗})(b^{∗})^{∗} et a^{∗}b^{∗} sont des expressions régulières.

Langage régulier (suite)

Le langage L(ξ) représenté par l’expression régulière ξ est défini par :

- L(∅) = ∅, L(ε) = {ε},

- L(a) = {a}, ∀a ∈ Σ,

- L(α + β) = L(α) ∪ L(β),

- L(αβ) = L(α) · L(β),

- L(α^{∗}) = L(α)^{∗}.

Th.: Un langage est régulier si et seulement si il est dénoté par une expression régulière.

Exemple : L’expression régulière a^{∗}(a+b^{∗})(b^{∗})^{∗} dénote le langage régulier {a}^{∗} · ({a} ∪ {b}^{∗})({b}^{∗})^{∗}.

Th.: L’ensemble des langages réguliers est dénombrable

Modélisation d’un ordinateur

Un ordinateur c’est :

- un processeur + des registres,

- une mémoire pour le programme,

- une mémoire pour les données. Cycle : exécuter une instruction du programme sur l’ensemble registres + mémoire. Etat : registres + mémoire. Cycle : fonction de transition sur les états. Le couple fonction de transition + état initial détermine l’exécution du programme.

Modélisation d’un programme

Modélisation d’un programme sur un ordinateur :

- un ensemble fini d’états,

- une fonction de transition,

- un état initial. Modélisation de l’exécution d’un programme : séquence d’états obtenus par applications successives de la fonction de transition a l’état initial. Séquence infinie : préfixe + (séquence fini)^{∗}.

Modélisation d’un programme (suite)

Problème : nombre fini d’instances du problème (états initiaux) vs nombre infini d’instances d’un problème (mots d’un langage). Solutions:

- nombre d’états infini ou,

- introduire les instances du problème caractère par caractère via un ruban et une tête de lecture (choix provisoire). Cycle :

1. lecture d’un caractère,

2. application de la fonction de transition,

3. déplacement de la tête de lecture.

Automate fini déterministe

Description informelle d’un AFD

- une tête de lecture qui indique le caractère suivant à lire sur le ruban d’entrée 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.

Exécution informelle d’un AFD:

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

- A chaque étape : lecture du caractère, application de la fonction de transition, déplacement de la tête de lecture ;

- Arrêt : Le mot est accepté si l’automate est dans un état accepteur.

Description formelle d’un AFD

Soit M = (Q, Σ, δ, s, F)

- Q est un ensemble fini d’états,

- Σ est un alphabet,

- δ : Q × Σ → Q la fonction de transition,

- s ∈ Q l’état initial,

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

M est un automate fini déterministe.

Le couple (q, w) ∈ Q × Σ^{∗} est une configuration.

La configuration (q′, w′) est dérivable en une étape de la configuration (q, w) par l’AFD M (noté (q, w) ⊢_{M} (q′, w′)) si, par définition, w = σw′, σ ∈ Σ et q′ = δ(q, σ).

Description formelle d’un AFD (suite)

La configuration (q′, w′) est dérivable de la configuration (q, w) par l’AFD M (noté (q, w) ⊢_{M}^{∗} (q′, w′)) si, par définition, il existe k ≥ 0 et des configurations (q_{i}, w_{i}), 0 ≤ i ≤ k telles que

- (q, w) = (q_{0}, w_{0}),

- (q′, w′) = (q_{k}, w_{k}),

- ∀i, 0 ≤ i ≤ k, (q_{i}, w_{i}) ⊢_{M} (q_{i+1} , w_{i+1} ).

L’exécution d’un automate M sur un mot w est la suite des configurations (s, w) ⊢_{M} (q_{1}, w_{1}) ⊢_{M} … ⊢_{M} (q_{n}, ε).

Un mot est accepté par un AFD M si (s, w) ⊢_{M}^{∗} (q, ε) avec q ∈ F.

Le langage accepté par un AFD M est l’ensemble L(M) des mots acceptés par M.

Exemples d’AFD

exe.: Soit l’AFD M suivant : Q = {q_{0}, q_{1}}, Σ = {a, b}, s = q_{0}, F = {q_{1}}, δ définie par :

\begin{matrix}q & q_{0} & q_{0} & q_{1} & q_{1} \\ σ & a & b & a & b \\ δ(q, σ) & q_{0} & q_{1} & q_{0} & q_{1} \end{matrix}

L(M) = {w | w se termine par b}.

Exemple : Construire un AFD M′ sur l’alphabet {a, b} qui accepte le langage L(M′) = {w | w ne contient pas consécutivement 2 a}.

Automate fini non déterministe

Description informelle d’un AFND Les AFND sont des AFD où l’on permet plusieurs transitions correspondant à la même lettre dans chaque état.

Les ε-AFND sont des AFND où l’on permet des transitions sur ε (i.e. sans avancer la tête de lecture).

(On permet parfois des transitions sur des mots de longueur supérieur à 1.)

Description formelle d’un AFND

Soit M = (Q, Σ, Δ, s, F)

- Q est un ensemble fini d’états,

- Σ est un alphabet,

- Δ ⊂ (Q × Σ × Q) la relation de transition,

- s ∈ Q l’état initial,

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

M est un automate fini non déterministe.

Les autres définitions sont étendues de façon immédiate.

Exemple : Construire un AFND M sur l’alphabet {a, b} qui accepte le langage L(M) = {w | w se termine par ab}.

Équivalence d’automates

Deux automates M et M′ sont équivalents si ils acceptent le Mme langage (i.e. L(M) = L(M′)).

Th.: Pour tout AFND il existe un AFD équivalent.

Const.: Soit un AFND M = (Q, Σ, Δ, s, F), nous construisons un AFD M′ = (Q′, Σ′, δ′, s′, F′) équivalent à M de la manière suivante

- Q′ = 2^{Q}, Σ′ = Σ, s′ = {s},

- δ′(\overline{q}, a) = ⋃\{p ∈ Q | ∃q ∈ \overline{q}, (q, a, p) ∈ Δ\},

- F′ = \{\overline{q} ∈ Q′ | \overline{q} ∩ F ≠ ∅\}.

Exemple : Construire un AFD équivalent à l’AFND suivant :

M = ( \begin{matrix}\{q_{0}, q_{1}\}, \{0, 1\}, \{(q_{0}, 0, q_{0}), (q_{0}, 0, q_{1}), \\ (q_{0}, 1, q_{1}), (q_{1}, 1, q_{0}), (q_{1}, 1, q_{1})\}, q_{0}, \{q_{1}\}). \end{matrix}

Th.: Pour tout ε-AFND il existe un AFND équivalent.

Grammaire

Soit G = (V, Σ, R, S) tel que

- V est un alphabet,

- Σ ⊆ V est l’ensemble des symboles terminaux (V −Σ est l’ensemble des symboles non terminaux),

- R ⊆ (V^{+} × V^{∗}) est un ensemble fini de règles ((u, v) est noté u → v),

- S ∈ V − Σ le symbole de départ.

G est une grammaire.

Exemple : V = \begin{aligned}\{ & P hrase, Sujet, V erbe, P ronom, \\ & il, elle, dort, écoute\}, \end{aligned}

Σ = {il, elle, dort, écoute},

R = \begin{aligned}\{ & P hrase → Sujet V erbe & Sujet → P ronom \\ & P ronom → il & P ronom → elle \\ & V erbe → dort & V erbe → écoute\}, \end{aligned}

S = P hrase

G_{f} = (V, Σ, R, S) est une grammaire.

Grammaires (suite)

Soit une grammaire G = (V, Σ, R, S) et u ∈ V^{+} , v ∈ V^{∗}. La grammaire G permet de dériver v de u en une étape (u ⇒ v) si

- u = xu′y,

- v = xv′y et

- u′ → v′

Exemple : Sujet V erbe P ronom ⇒ Sujet dort P ronom en effet en posant x = Sujet, y = P ronom, u′ = V erbe et v′ = dort, nous avons V erbe → dort ∈ R.

Soit une grammaire G = (V, Σ, R, S) et u ∈ V^{+} , v ∈ V^{∗}. La grammaire G permet de dériver v de u en plusieurs étapes (u ⇒^{∗} v) si ∃k ≥ 0 et v_{0}, …, v_{k} ∈ V^{+} tels que

- u = v_{0},

- v = v_{k} et

- v_{i} ⇒ v_{i+1} , 0 ≤ i < k.

Grammaire (suite)

Exemple : P ronom dort elle est dérivable de Sujet V erbe Sujet par la grammaire G_{f}

(Sujet V erbe Sujet ⇒^{∗} P ronom dort elle)

règles

Sujet V erbe Sujet  Sujet → P ronom
Sujet V erbe P ronom V erbe → dort
Sujet dort P ronom  Sujet → P ronom
P ronom dort P ronom P ronom → elle

P ronom dort elle

Un mot v ∈ Σ^{∗} est généré par une grammaire G si S ⇒^{∗} v.

Exemple : Le mot elle dort est généré par la grammaire G_{f} :

règles

P hrase  P hrase → Sujet V erbe
Sujet V erbe V erbe → dort
Sujet dort Sujet → elle

elle dort

Grammaire (suite)

Le langage généré par une grammaire G L(G) = {v ∈ Σ^{∗} tel que S ⇒^{∗} v}. Exemple : L(G_{f}) = {il dort, il écoute, elle dort, elle écoute}. Exemple : Soit la grammaire

G = \begin{matrix}(\{S, a, b, A, B\}, \{a, b\}, \\ \{S → ε, S → aB, \\ S → bA, A → aS, \\ A → bAA, B → bS, \\ B → aBB\}, S). \end{matrix}

Démontrez que L(G) est l’ensemble des mots comportant le meme nombre de lettres a et de lettres b.

Typologie des grammaires

4 types de grammaires :

- type 0 : grammaires générales,

- type 1 : grammaires sensibles au contexte,

- type 2 : grammaires hors contexte,

- type 3 : grammaires régulières.

Th.: type 3 ⊂ type 2 ⊂ type 1 ⊂ type 0.

Une grammaire est régulière si toute production est de la forme A → wB ou A → w avec A, B ∈ V − Σ et w ∈ Σ^{∗}.

Caractérisation des langages réguliers

Th.: Un langage est régulier ssi il est accepté par un automate fini ssi il est généré par une grammaire régulière.

Expression régulière : descriptif, Automate fini : analytique, Grammaire régulière : génératif.

Langage régulier ⇒ automate fini

Const.: Construisons par induction un AFND M_{ξ} à partir d’une expression régulière ξ (M_{i} = (Q_{i}, Σ_{i}, Δ_{i}, s_{i}, F_{i}) automate pour l’expression régulière α_{i}) :

- si ξ = ∅ alors M_{ξ} = ({q}, ∅, ∅, q, ∅)

- si ξ = ε alors M_{ξ} = ({q}, ∅, ∅, q, {q})

- si ξ = σ ∈ Σ alors M_{ξ} = ({q_{0}, q_{1}}, {σ}, {(q_{0}, σ, q_{1})}, q_{0}, {q_{1}})

- si ξ = α_{1}α_{2} alors

M_{ξ} = ( \begin{matrix}Q_{1} ∪ Q_{2}, Σ_{1} ∪ Σ_{2}, \\ Δ_{1} ∪ Δ_{2} ∪ \{(q, ε, s_{2})/q ∈ F_{1}\}, s_{1}, F_{2}) \end{matrix}

- si ξ = α_{1}^{∗} alors

M_{ξ} = ( \begin{matrix}Q_{1} ∪ \{s\}, Σ_{1}, Δ_{1} ∪ \{(q, ε, s_{1})/q ∈ F_{1}\}, \\ s, F_{2} ∪ \{s\}) \end{matrix}

- si ξ = α_{1} + α_{2} alors

M_{ξ} = ( \begin{matrix}Q_{1} ∪ Q_{2} ∪ \{s\}, Σ_{1} ∪ Σ_{2}, \\ Δ_{1} ∪ Δ_{2} ∪ \{(s, ε, s_{1}), (s, ε, s_{2})\}, s, F_{1} ∪ F_{2}) \end{matrix}

Automate fini ⇒ Grammaire régulière

Const.: Construisons une grammaire régulière G = (V_{G}, Σ_{G}, S_{G}, R_{G}) à partir d’un AFND M = (Q, Σ, Δ, s, F) telle que L(G) = L(M) comme suit :

- V_{G} = Q ∪ Σ

- Σ_{G} = Σ

- S_{G} = s

- R_{G} = \begin{matrix}\{A → wB/(A, w, B) ∈ Δ\}∪ \\ \{A → ε/A ∈ F \} \end{matrix}

Grammaire régulière ⇒ Automate fini

Const.: Construisons un AFND M = (Q, Σ, Δ, s, F) à partir d’une grammaire régulière G = (V_{G}, Σ_{G}, S_{G}, R_{G}) tel que L(M) = L(G) comme suit :

- Q = (V_{G} − Σ_{G}) ∪ {f}, (f ∉ V_{G}),

- Σ = Σ_{G},

- s = S_{G},

- F = {f},

- Δ = \begin{matrix}\{(A, w, B)/A → wB ∈ R_{G}\}∪ \\ \{(A, w, f)/A → w ∈ R_{G}\} \end{matrix}

Théorème du gonflement et langages non

réguliers

Th.: Soit L un langage régulier infini. Alors ∃u, v, w ∈ Σ^{∗}, v ≠ ε tels que ∀n ≥ 0, uv^{n}w ∈ L.

Pr. Inf. Soit M = (Q, Σ, δ, s, F) avec | Q |= m et x ∈ L(M) tel |x|> m. Alors ∃q ∈ Q, uvw ∈ Σ^{∗} et f ∈ F tels que x = uvw et (s, x) ⊢_{M}^{∗} (q, vw) ⊢_{M}^{∗} (q, w) ⊢_{M}^{∗} (f, ε) donc uv^{∗}w ∈ L(M).

Th.: Soit L un langage régulier infini et soit x ∈ L tel que |x|≥|Q|, Q ensemble des états d’un automate non déterministe acceptant L. Alors ∃u, v, w ∈ Σ^{∗}, v ≠ ε, | uv|≥|Q| tels que uvw = x et ∀n ≥ 0, uv^{n}w ∈ L.

ex.: Le langage L = a^{n^{2}} n’est pas régulier.

ex.: Le langage L = {a^{n} | n premier} n’est pas régulier.

ex.: Le langage L = a^{n}b^{n} n’est pas régulier.

Automates à pile

Soit M = (Q, Σ, Γ, Δ, Z, s, F)

- Q est un ensemble fini d’états,

- Σ est un alphabet d’entrée,

- Γ est un alphabet de pile,

- Δ ⊂ ((Q × Σ^{∗} × Γ^{∗}) × (Q × Γ^{∗})) la relation de transition (ensemble fini),

- Z ∈ Γ est le symbole initial de la pile,

- s ∈ Q l’état initial,

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

M est un automate à pile.

Exemple : Soit P_{1} = ({s, p, q}, {a, b}, {A, Z}, Δ, Z, s, {q})

avec Δ :\{ \begin{matrix}((s, a, ε), (s, A)) \\ ((s, ε, Z), (q, ε)) \\ ((s, b, A), (p, ε)) \\ ((p, b, A), (p, ε)) \\ ((p, ε, Z), (q, ε))\} \end{matrix}

P_{1} est un automate à pile.

Automates à pile (suite)

Le triplet (q, u, β) ∈ Q×Σ^{∗}×Γ^{∗} est une configuration.

La configuration (q′, w′, α′) est dérivable en une étape de la configuration (q, w, α) par l’automate à pile M (noté (q, w, α) ⊢_{M} (q′, w′, α′)) si w = uw′, u ∈ Σ^{∗}, α = βδ, β, δ ∈ Γ^{∗}, α′ = γδ, γ ∈ Γ^{∗}, et ((q, u, β), (q′, γ)) ∈ Δ.

Exemple : (p, baba, AAZ) ⊢_{P_{1}} (p, aba, AZ) par :

- p = q, p = q′, w = baba, w′ = aba, α = AAZ, α′ = AZ,

- u = b, β = A, γ = ε, δ = AZ,

- ((p, b, A), (p, ε)) ∈ Δ,

Une configuration C′ est dérivable en plusieurs étapes de la configuration C par l’automate à pile 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.

Automates à pile (suite)

L’exécution d’un automate à pile M sur un mot w est la suite des configurations (s, w, Z) ⊢_{M} (q_{1}, w_{1}, α_{1}) ⊢_{M} … ⊢_{M} (q_{n}, ε, γ).

Exemple : (s, aabb, Z) ⊢_{P_{1}}^{∗} (q, ε, Z) :

configurations transitions
(s, aabb, Z) ((s, a, ε), (s, A))
(s, abb, AZ) ((s, a, ε), (s, A))
(s, bb, AAZ) ((s, b, A), (p, ε))
(p, b, AZ)  ((p, b, A), (p, ε))
(p, ε, Z)  ((p, ε, Z), (q, ε))

(q, ε, ε)

Un mot est accepté par un automate à pile M si (s, w, Z) ⊢_{M}^{∗} (q, ε, γ) avec q ∈ F.

Exemple : Le mot aabb est accepté par l’automate à pile P_{1}.

Automates à pile (suite)

Le langage accepté par un automate à pile M est l’ensemble L(M) des mots acceptés par M. Exemple : L’automate à pile P_{1} accepte le langage {a^{n}b^{n}/n ≥ 0}. Exemple : Décrire un automate à pile qui accepte le langage {ww^{R}}.

Grammaires hors-contexte

Une grammaire est une grammaire hors-contexte si toutes les règles sont de la forme A → B, A ∈ V −Σ, B ∈ V^{∗}.

Exemple : La grammaire G_{1} = ({S, a, b}, {a, b}, R_{1}, S), R_{1} = {S → aSb, S → ε}, est hors-contexte et génère le langage {a^{n}b^{n}/n ≥ 0}.

Exemple : Décrire la grammaire qui génère le langage {ww^{R}}.

Caractérisation des langages hors-contexte

Th. Un langage est hors-contexte si et seulement si il est accepté par un automate à pile.

Const.: Grammaire hors-contexte ⇒ automate à pile. Soit la grammaire hors contexte G = (V_{G}, Σ, R_{G}, S_{G}), nous construisons l’automate à pile M = (Q, Σ, Γ, Δ, Z, s, F) tel que L(G) = L(M) de la manière suivante :

- Q = {s, q, r}, Γ = V ∪ {Z}, Z ∉ V,F = {r},

- Δ = \begin{matrix}\{((s, ε, ε), (q, S)), ((q, ε, Z), (r, ε))\}∪ \\ \{((q, ε, A), (q, x))/A → x ∈ R\}∪ \\ \{((q, a, a), (q, ε))/a ∈ Σ\} \end{matrix}

Théorème du gonflement et langage

hors-contexte

Th.: Soit un langage hors-contexte L. Alors il existe une constante K telle que tout mot w ∈ L satisfaisant | w|> K peut etre écrit w = uvxyz avec v ou y ≠ ε et uv^{n}xy^{n}z ∈ L, ∀n > 0.

exe.: Le langage L = {a^{n}b^{n}c^{n}} n’est pas hors-contexte.

rem.: L’intersection de deux langages hors-contexte n’est pas nécessairement hors-contexte : L_{1} = {a^{n}b^{m}c^{m}} et L_{2} = {a^{m}b^{m}c^{n}} sont hors-contexte mais L_{1} ∩ L_{2} = {a^{m}b^{m}c^{m}} n’est pas hors-contexte.

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

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.

Exemple : 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)

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.

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)

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.

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

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

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

Exécution d’une MT

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.

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

- M accepte L,

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

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

Langages acceptés,

langages décidés et automates

La notion de langage décidé n’est valable que pour des automates déterministes.

– Automate fini déterministe :

langage accepté ≡ langage décidé.

– Th.: Étant donné une grammaire hors-contexte G (et donc un automate à pile par le théorème d’équivalence), il existe un algorithme pour déterminer si un mot donné appartient à L(G).

– Automate à pile déterministe:

langage accepté ≡ langage décidé, si il n’y a pas de transition sur ε.

Thèse de Turing-Church

Une procédure effective est une solution à un problème qui a la forme d’un programme pouvant être exécuté sur un ordinateur en un temps fini pour toutes les entrées.

Thèse de Turing-Church : Les langages reconnus par une procédure effective sont exactement ceux décidés par une machine de Turing.

lem.: Tout langage décidé par une machine de Turing est reconnu par une procédure effective.

Conjecture : Pour tout langage reconnu par une procédure effective, il existe une machine de Turing qui le décide.

Extensions des Machines de Turing

- Ruban infini dans les deux sens,

- Rubans multiples,

- Machines à mémoire à accès direct.

Toutes ces machines peuvent être simulées par une machine de Turing.

- Machines de Turing non-déterministes (une relation de transition remplace la fonction de transition).

Th.: Tout langage accepté par une machine de Turing non-déterministe est aussi accepté par une machine de Turing déterministe.

Fonctions calculables par une machine de

Turing

Une machine de Turing calcule une fonction f : Σ^{∗} → Σ^{∗} si, pour tout mot d’entrée w, elle s’arrête toujours dans une configuration ou se trouve f(w) sur le ruban.

Thèse de Turing-Church : Les fonctions calculables par une procédure effective sont les fonctions calculables par une machine de Turing.

Exemple : Écrire une machine de Turing pour additionner deux nombres entiers dans une représentation binaire.

Fonctions Récursives

Approche basée sur les fonctions définies sur les nombres naturels pour caractériser celles qui sont calculables par une procédure effective.

Fonctions calculables connues :

- les fonctions de base dont un algorithme est connu pour les calculer sur une représentation ;

- la composition finie de fonctions de base ;

- la récursion (… en partie).

Exemple : Exemples de fonctions récursives :

- + et x sur les réels,

- la factorielle,

- la racine carré d’un réel positif par la méthode de Newton

Fonctions récursives primitives

Les fonctions récursives primitives simples sont :

- la fonction \overline{0},

- les fonctions de projection π_{i}^{k} = (λn_{1} … n_{k} n_{i}),

- la fonction successeur (λn (σ n)).

La composition de la fonction g à l arguments et des fonctions h_{1}, …, h_{l} à k arguments est la fonction f à k arguments définie par : (λn_{1} … n_{k} (g (h_{1} n_{1} … n_{k}) … (h_{l} n_{1} … n_{k}))).

La récursion primitive à partir des fonctions g à k arguments et h à k + 2 arguments est la fonction f à k + 1 arguments définie par :

(λ n_{1} … n_{k}m (if (m = (σ m′))
then (h (f n_{1} … n_{k} m′) n_{1} … n_{k} m′)
else (g n_{1} … n_{k})))

Fonctions récursives primitives (suite)

Les fonctions récursives primitives sont définies inductivement par :

- les fonctions récursives primitives simples,

- la composition et la récursion primitive.

Exemple : Les fonctions constantes \overline{j} sont des fonctions primitives récursives : \overline{j} = \underbrace{(σ (σ … (σ \overline{0})))}_{j fois}.

Exemple : L’addition, la soustraction et la multiplication sur les naturels sont des fonctions récursives primitives.

Exemple : La factorielle est une fonction récursive primitive.

Exemple : Le produit borné par m d’une fonction (λn_{1} … n_{k}i (g n_{1} … n_{k} i)) défini par le produit de g pour les m premières valeurs de i est une fonction récursive primitive.

Les prédicats récursifs primitifs

Un prédicat à k arguments est un sous-ensemble de ℕ^{k}.

La fonction caractéristique d’un prédicat P ⊆ ℕ^{k} est la fonction f_{P} de ℕ^{k} dans {0, 1} définie par :

\begin{matrix}(f_{P} n_{1} … n_{k}) = & \overline{0} si (n_{1}, …, n_{k}) ∉ P \\ \overline{1} & sinon \end{matrix}

Un prédicat est récursif primitif si sa fonction caractéristique est récursive primitive.

Exemple : Le prédicat nonzero qui est vrai sauf si son argument est l’entier 0 a pour fonction caractéristique f_{\overline{0̸}} :

(λm (if (m = (σ m′))
then (π_{3}^{3} (f_{\overline{0̸}} m′) m′ \overline{1})
else \overline{0}))

Exemple : Écrire les fonctions caractéristiques (récursives primitives) des prédicats et, ou et non.

Les prédicats récursifs primitifs (suite)

La quantification bornée universelle teste si un prédicat est vrai pour toutes les valeurs d’un de ses arguments inférieures à une borne.

prop.: La quantification bornée universelle est un prédicat récursif primitif.

Soit f_{P} la fonction caractéristique du prédicat P à k+1 arguments. Alors la fonction caractéristique (récursive primitive) de la quantification bornée de P pour le k+1 argument ∀_{P}^{≤} est définie par : (λn_{1} … n_{k}m (if (m = (σ m′))

then (fois \begin{matrix}(π_{1}^{k+2} (∀_{P}^{≤} n_{1} … n_{k} m′) n_{1} … n_{k} m′) \\ (f_{P} n_{1} … n_{k} m′)) \end{matrix}

else (π_{1}^{k+2} \overline{1} n_{1} … n_{k} m′)))

Les prédicats récursifs primitifs (suite)

La quantification bornée existentielle teste si un prédicat est vrai pour des valeurs d’un de ses arguments inférieures à une borne.

prop.: La quantification bornée existentielle est un prédicat récursif primitif.

Pour une borne, la valeur de la fonction de minimisation bornée d’un prédicat (pour un de ses arguments) est le plus petit nombre naturel inférieur à la borne tel que le prédicat soit vrai :

μ_{P} i ≤ m = \{ \begin{matrix}le plus petit i ≤ m tel que \\ (n_{1}, …, n_{k}, i) ∈ P \\ 0 si il n’existe pas de tel i \end{matrix}

prop.: La minimisation bornée est une fonction récursive primitive.

Les fonctions μrécursives

Th.: Il existe des fonctions calculables qui ne sont pas primitives récursives.

La valeur de la fonction de minimisation non bornée d’un prédicat (pour un de ses arguments) est le plus petit nombre naturel tel que le prédicat soit vrai.

remarque : Dans le cas d’un prédicat toujours faux, la minimisation non bornée n’est pas calculable car ne termine jamais.

Un prédicat P est sûr si pour tout n_{1}, …, n_{k}, il existe un i tel que (n_{1}, …, n_{k}, i) ∈ P.

Les fonctions μrécursives sont celles obtenues par induction sur les fonctions récursives primitives simples, la composition, la récursion primitive et la minimisation non bornée des prédicats sûrs.

Fonctions μrécursives et Machines de Turing

2 approches pour la définition des fonctions calculables par des procédures effectives : les fonctions μrécursives et les fonctions calculables par machine de Turing.

Question : Les fonctions μrécursives sont-elles exactement les fonctions calculables par une machine de Turing?

Fonctions μrécursives Machine de Turing
sur les naturels  sur les caractères

Problème de la représentation effective des nombres par des caractères et inversement : nécessité de procédures effectives de codage.

Nombres et caractères

lem.: Il existe une représentation effective des nombres naturels par des chaînes de caractères.

pr. inf.: Le codage binaire des naturels.

lem.: Il existe une représentation effective des chaînes de caractères par des nombres naturels.

(la Gödelisation) La représentation d’une chaîne de caractère par un nombre de Gödel.

Exemple : Soit A un alphabet. Nous définissons une bijection gd de A dans {1, …, | A |}. Pour tout mot w = σ_{0} … σ_{l} ∈ A^{∗}, le nombre de Gödel de w est défini par :

Gd(w) = Σ_{i=0}^{l} (1+ |A|)^{l−i}gd(w_{i}).

Fonctions μrécursives ≡

machines de Turing

Th.: Toute fonction μrécursive est calculable par une machine de Turing.

pr. inf.: En adoptant un codage des entiers narurels, les fonctions primitives récursives simples, leurs compositions, leurs récursions primitives et leurs minimisations non bornées sûres sont calculables par une machine de Turing.

Th.: Toute fonction calculable par une machine de Turing est μrécursive.

pr. inf.: Soient une machine de Turing M sur un alphabet A calculant une fonction f_{M} de A^{∗} dans A^{∗} et une gödédisation Gd pour A^{∗}. Alors il existe une fonction μrécursive f telle que (∀w ∈ A^{∗}(f_{M}(w) = Gd^{−1}(f(Gd(w))))).

Fonctions partielles

Une fonction partielle f de A^{∗} dans A^{∗} est calculée par une machine de Turing M si,

- pour tout mot d’entrée w tel que f soit définie, M s’arrête toujours dans une configuration ou se trouve f(w) sur le ruban ;

- pour tout mot d’entrée w tel que f ne soit pas définie, M ne s’arrête pas ou s’arrête sur une configuration conventionnelle.

Une fonction partielle f de ℕ dans ℕ est μrécursive si elle est définie par induction sur les fonctions récursives primitives simples, la composition, la récursion primitive et la minimisation non bornée.

Th.: Une fonction partielle est μrécursive si et seulement si elle est calculable par une machine de Turing.

De la décidabilité à l’indécidabilité

La classe de décidabilité R est l’ensemble des langages décidés par une machine de Turing (ou récursifs ou décidables ou calculables ou solubles algorithmiquement).

La classe de décidabilité RE est l’ensemble des langages acceptés par une machine de Turing (ou récursivement énumérables ou semidécidables ou partiellement décidables ou partiellement calculables ou partiellement solubles algorithmiquement).

\begin{matrix}- L’ensemble des machines \\ de Turing est dénombrable. \\ - L’ensemble des langages \\ est non dénombrable. \end{matrix} \} alors il y a des langages indécidables.

lem.: R ⊆ RE.

Premier langage indécidable

Construisons le tableau A, qui compose toute machine de Turing avec tout mot, défini par :

- A[M_{i}, w_{j}] = oui si la machine de Turing M_{i} accepte le mot w_{j}.

- A[M_{i}, w_{j}] = non si la machine de Turing M_{i} rejette ou boucle pour le mot w_{j}.

Th.: Soit le langage L_{0} défini par

L_{0} = {w/w = w_{i} et A[M_{i}, w_{i}] = non}.

Alors L_{0} ∉ RE.

Diagonalisation : Posons que M_{k} accepte L_{0}.

M_{k} accepte w_{k} (w_{k} ∈ L_{0})
⇒ A[M_{k}, w_{k}] = oui ⇒ w_{k} ∉ L_{0}
M_{k} n’accepte pas w_{k} (w_{k} ∉ L_{0})
⇒ A[M_{k}, w_{k}] = non ⇒ w_{k} ∈ L_{0}

Double contradiction donc il n’existe pas de machine de Turing qui accepte L_{0} (L_{0} ∉ RE).

Propriétés des classes l’indécidabilité

lem.: L ∈ R si et seulement si \overline{L} ∈ R.

pr. inf.: Soit M_{L} une MT qui décide du langage L. Construisons la MT M qui rejette un mot lorsque M_{L} l’accepte et qui accepte un mot lorsque M_{L} le rejette (toujours en un temps fini). Alors M décide de \overline{L}.

lem.: Si L ∈ RE et \overline{L} ∈ RE alors L ∈ R et \overline{L} ∈ R.

pr. inf.: Soient les MT M_{L} qui accepte L et M\overline{L} qui accepte \overline{L}. Construisons la MT M qui accepte un mot lorsque M_{L} accepte un mot ou M\overline{L} termine en le rejetant et qui rejette un mot lorsque M\overline{L} accepte un mot ou M_{L} termine en le rejetant. Alors M décide de L.

Un langage de RE ∩ \overline{R}

cor.: Soit L un langage. Alors

- soit L ∈ R et \overline{L} ∈ R

- soit L ∉ RE et \overline{L} ∉ RE

- soit L ∉ RE et \overline{L} ∈ RE ∩ \overline{R}

lem.: \overline{L_{0}} ∈ RE.

pr. inf.: Construisons une machine de Turing universelle (qui simule le fonctionnement d’une machine de Turing M donnée sur un mot w donné) qui :

- Énumère les mots pour obtenir w;

- Énumère les machines de Turing pour obtenir M ;

- Simule M_{i} sur M pour w. M accepte w si il est accepté par M_{i}.

cor.: \overline{L_{0}} ∈ RE ∩ \overline{R}.

Technique de réduction

La technique de réduction établit l’indécidabilité d’un langage L à partie de l’indécidabilité d’un langage L′ en exhibant une procédure effective (dite de réduction de L′ à L) qui décide de L′ si L est décidable.

\begin{matrix}L ∈ R ⇒ L′ ∈ R \\ L′ ∉ R \end{matrix} \} ⇒ L ∉ R.

Exemple : Soit le langage universelle LU défini par

LU = {< M, w > /M accepte w}.

LU ∈ RE ∩ \overline{R} (et \overline{LU} ∉ RE).

Exemple : Les problèmes de l’arrêt, de l’arrêt dans un langage de programmation, de l’arrêt sur le mot vide, de l’arrêt pour au moins un mot et de l’arrêt pour tout mot sont indécidables.

Exemple : Le problème de déterminer si le langage accepté par une machine de Turing est vide est indécidable.

Propriétés des langages récursivement

énumérables

Soit une machine de Turing M. Le langage calculé par M est défini par

{w/∃u, M s’arrête sur u avec w sur le ruban}.

Th.: Un langage est calculé par une machine de Turing si et seulement si il est accepté par une machine de Turing.

Th.: Un langage est généré par une grammaire si et seulement si il est accepté par une machine de Turing.

Résumé sur la calculabilité

- Les langages réguliers sont générés par les grammaires régulières (T3) et décidés par les automates d’états finis déterministes.

- Les langages hors-contexte sont générés par les grammaires hors-contexte (T2), acceptés par les automates à piles et décidés par les machines de Turing.

- Les langages sensibles au contexte sont générés par les grammaires sensibles au contexte (T1) (acceptés par les automates à borne linéaire) et décidés par les machines de Turing.

- Les langages généraux sont générés par les grammaires non restreintes (T0) et acceptés par les machines de Turing.