Notation

Soit un programme $M$, alors on note $\langle M \rangle$ la chaîne de symboles qui représente $M$.

Différence entre $M$ et $\langle M \rangle$

Lorsque l’on parle d’un « programme » on ne fait souvent pas la distinction entre le code source du programme et l’exécutable qui lui correspond.

La différence entre $M$ et $\langle M \rangle$ est de la même nature.

• $M$ est une « machine » donc un processus automatique, un exécutable, quelque chose qui reçoit une entrée et retourne (peut-être) une sortie.
• $\langle M \rangle$ est une suite de 0 et de 1. On choisit d’interpréter cette suite de 0 et de 1 comme ayant un sens précis, celui de l’encodage de $M$.

La Trahison des images (1929, huile sur toile, 59 × 65 cm), René Magritte

$A_{\text{AFD}}$

$$A_{\text{AFD}} = \{\langle B, w\rangle \mid B \text{ est un AFD qui accepte } w\}$$

$\text{AFD}$: automate fini déterminite

Théorème

$A_{\text{AFD}}$ est un langage décidable.

Démonstration

Soit la machine de Turing $M_{A_{\text{AFD}}}$ qui décide $A_{\text{AFD}}$.

$M_{A_{\text{AFD}}} = $ Avec $\langle B, w\rangle$

1. Simuler $B$ sur $w$.
2. Si la simulation termine sur un état accepteur alors $\mathtt{ACCEPTE}$. Si la simulation termine sur un état non-accepteur alors $\mathtt{REJETTE}$.

$A_{\text{AFN}}$

$$A_{\text{AFN}} = \{\langle B, w\rangle \mid B \text{ est un AFN qui accepte } w\}$$

$\text{AFN}$: automate fini non déterminite

Théorème

$A_{\text{AFN}}$ est un langage décidable.

Démonstration

Soit la machine de Turing $M_{A_{\text{AFN}}}$ qui décide $A_{\text{AFN}}$.

$M_{A_{\text{AFN}}} = $ Avec $\langle B, w\rangle$

1. Covertir $B$ en $C$ un $\text{AFD}$ équivalent.
2. Executer $M_{A_{\text{AFD}}}$ sur $\langle C, w\rangle$
3. Si $M_{A_{\text{AFD}}}$ accepte alors $\mathtt{ACCEPTE}$ sinon $\mathtt{REJETTE}$.

$E_{\text{AFD}}$

$$E_{\text{AFD}} = \{\langle B \rangle \mid B \text{ est un AFD et } L(B) = \emptyset\}$$

Théorème

$E_{\text{AFD}}$ est un langage décidable.

Démonstration

Soit la machine de Turing $M_{E_{\text{AFD}}}$ qui décide $E_{\text{AFD}}$.

$M_{E_{\text{AFD}}} = $ Avec $\langle B \rangle$

1. Marquer l'état initial de $B$.
2. Répéter jusqu'à ce qu'il n'y est plus d'état à marquer
   1. Marquer un état pour lequel il existe une transition venant d'un état déjà marqué.
3. Si aucun état accepteur de $B$ n'est marqué alors $\mathtt{ACCEPTE}$ sinon $\mathtt{REJETTE}$.

$EQ_{\text{AFD}}$

$$EQ_{\text{AFD}} = \{\langle A, B \rangle \mid A \text{ et } B \text{ sont des AFD et } L(A) = L(B) \}$$

Théorème

$EQ_{\text{AFD}}$ est un langage décidable.

Théorie des ensembles

Soit $C$ un $\text{AFD}$ tel que $$L(C) = \big( L(A) \cap \overline{L(B)} \big) \cup \big( \overline{L(A)} \cap L(B) \big)$$

$$L(A) = L(B) \ \Leftrightarrow \ L(C) = \emptyset$$

Démonstration

Soit la machine de Turing $M_{EQ_{\text{AFD}}}$ qui décide $EQ_{\text{AFD}}$.

$M_{EQ_{\text{AFD}}} = $ Avec $\langle A, B \rangle$

1. Construire l'automate fini déterministe $C$ à partir de $A$ et $B$.
2. Executer $M_{E_{\text{AFD}}}$ sur $\langle C \rangle$
3. Si $M_{E_{\text{AFD}}}$ accepte alors $\mathtt{ACCEPTE}$ sinon $\mathtt{REJETTE}$.

$A_{\text{GHC}}$

$$A_{\text{GHC}} = \{\langle G, w\rangle \mid G \text{ est une GHC qui génère } w\}$$

$\text{GHC}$: grammaire hors context

Théorème

$A_{\text{GHC}}$ est un langage décidable.

Forme normale de Chomsky

Définition: Soit $G = (V, \Sigma, S, R)$ une grammaire. $G$ est dans la forme normale de Chomsky si les règles de réécriture sont de la forme:

• $A \to BC$ pour $A, B, C \in V$ et $B \ne S$ et $C \ne S$
• $A \to a$ pour $A \in V$, $a \in \Sigma$.
• $S \to \lambda$ pour le symbole de départ $S$.

Démonstration

Soit la machine de Turing $M_{A_{\text{GHC}}}$ qui décide $A_{\text{GHC}}$.

$M_{A_{\text{GHC}}} = $ Avec $\langle G, w\rangle$

1. Convertir $G$ à une grammaire équivalente dans la forme normale de Chomsky
2. Lister toutes les dérivations de $2n-1$ productions (ou de seulement une production si $w = \lambda$)
3. Si un des mots générés est $w$ alors $\mathtt{ACCEPTE}$ sinon $\mathtt{REJETTE}$.

$E_{\text{GHC}}$

$$E_{\text{GHC}} = \{\langle G \rangle \mid G \text{ est une GHC et } L(G) = \emptyset\}$$

Théorème

$E_{\text{GHC}}$ est un langage décidable.

Démonstration

Soit la machine de Turing $M_{E_{\text{GHC}}}$ qui décide $E_{\text{GHC}}$.

$M_{E_{\text{GHC}}} = $ Avec $\langle G \rangle$

1. Marquer tous les symboles terminaux de $G$.
2. Répéter jusqu'à ce qu'il n'y est plus de variables à marquer
   1. Marquer une variable $A$ tel que $G$ a une règle $A \to U_1 \cdots U_k$ et que les symboles $U_1, \dots, U_k$ sont tous marqués.
3. Si la variable initiale est marquée alors $\mathtt{ACCEPTE}$ sinon $\mathtt{REJETTE}$.

$EQ_{\text{GHC}}$

$$EQ_{\text{GHC}} = \{\langle G, H \rangle \mid G \text{ et } H \text{ sont des GHC et } L(G) = L(H) \}$$

Problème

Les langages hors contexte ne sont pas fermés sur les opérations complément et intersection.

Théorème

Soit le langage $L$.

$$L \text{ est hors contexte} \Rightarrow L \text{ est décidable}$$

Démonstration

$L$ est hors contexte si il exite une grammaire $G$ qui génère $L$.

Soit la machine de Turing $M_{G}$ qui décide $L(G)$.

$M_{G} = $ Avec $\langle w \rangle$

1. Exécuter $M_{A_{\text{GHC}}}$ sur $\langle G, w \rangle$
2. Si $M_{A_{\text{GHC}}}$ accepte alors $\mathtt{ACCEPTE}$ sinon $\mathtt{REJETTE}$.

$A_{\text{MT}}$

$$A_{\text{MT}} = \{\langle M, w\rangle \mid M \text{ est une machine de Turing qui accepte } w\}$$

$\text{MT}$: machine de Turing

Théorème

$A_{\text{TM}}$ est un langage Turing-acceptable.

Théorème

$A_{\text{TM}}$ n'est pas un langage décidable.

Corrolaire

$\overline{A_{\text{TM}}}$ n'est pas un langage Turing-acceptable.

$HALT_{\text{MT}}$

$$HALT_{\text{MT}} = \{\langle M, w \rangle \mid M \text{ est une MT et } M \text{ s'arrête sur } w \}$$

Théorème

$HALT_{\text{MT}}$ n'est pas un langage décidable.

Théorème

Si $A \le_m B$ et $B$ est décidable, alors $A$ est décidable.

Corrolaire

Si $A \le_m B$ et $A$ n'est pas décidable, alors $B$ n'est pas décidable.

$E_{\text{MT}}$

$$E_{\text{MT}} = \{\langle M \rangle \mid M \text{ est une MT et } L(M) = \emptyset \}$$

Théorème

$A_{\text{MT}} \le_m E_{\text{MT}}$

Ceci implique que $E_{\text{MT}}$ n'est pas un langage décidable.

$REGULIER_{\text{MT}}$

$$REGULIER_{\text{MT}} = \{\langle M \rangle \mid M \text{ est une MT et } L(M) \text{ est régulier} \}$$

Théorème

$A_{\text{MT}} \le_m REGULIER_{\text{MT}}$

Ceci implique que $REGULIER_{\text{MT}}$ n'est pas un langage décidable.

$EQ_{\text{MT}}$

$$EQ_{\text{MT}} = \{\langle M_1, M_2 \rangle \mid M_1 \text{ et } M_2 \text{ sont des MT et } L(M_1) = L(M_2) \}$$

Théorème

$E_{\text{MT}} \le_m EQ_{\text{MT}}$

Ceci implique que $EQ_{\text{MT}}$ n'est pas un langage décidable.

Théorème

Si $A \le_m B$ et $B$ est Turing-acceptable, alors $A$ est Turing-acceptable.

Corrolaire

Si $A \le_m B$ et $A$ n'est pas Turing-acceptable, alors $B$ n'est pas Turing-acceptable.

Corrolaire

Si $A \le_m B$ et $\overline{A}$ n'est pas Turing-acceptable, alors $\overline{B}$ n'est pas Turing-acceptable.

co-Turing-acceptable

Définition: Un langage $L$ est dit co-Turing-acceptable si $\overline{L}$ est Turing-acceptable.

Example

$A_{\text{MT}}$ est Turing-acceptable.

$A_{\text{MT}}$ n'est pas co-Turing-acceptable.

Corrolaire

Si $A \le_m B$ et $A$ n'est pas co-Turing-acceptable, alors $B$ n'est pas co-Turing-acceptable.

Théorème

$E_{\text{MT}}$ n'est ni Turing-acceptable ni co-Turing-acceptable

Démonstration

$$A_{\text{MT}} \le_m EQ_{\text{MT}} \ \Rightarrow \ EQ_{\text{MT}} \text{ n'est pas co-Turing-acceptable}$$

$$A_{\text{MT}} \le_m \overline{EQ_{\text{MT}}} \ \Rightarrow \ EQ_{\text{MT}} \text{ n'est pas Turing-acceptable}$$