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

def 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).

def 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

def 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

def 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.