• H n'est pas récursif
• Il existe des langages récursivement énumérables qui ne sont pas récursifs
• La classe des langages récursivement énumerables n'est pas stable par complément
• Exemple :
  • H n'est pas récursif et \bar{H} n'est pas récursivement énumerable.

• Problème indécidable correspond à un langage non-récursif. C'est à dire qu'il n'existe pas de MT qui décide le langage ⇔ il n'existe pas d'algorithme qui résout le problème.
• Exemple : H n'est pas récursif ⇔ l'arrêt n'est pas décidable

Pour pouvoir démontrer que d'autres problèmes sont indécidables, nous allons employer la réduction de problèmes : montrer que résoudre un nouveau problème permettrait de résoudre un problème qu'on sait déjà indécidable, et d'en conclure que le nouveau doit l'être aussi.

Si \rho est une réduction de L₁ à L₂

• si L₂ est récursif alors L₁ est récursif
• si L₁ n'est pas récursif alors L₂ n'est pas récursif non plus.

Soit M_{\rho} une MT qui implante \rho (qui est récursif).

• Y : \rho\left(w\right) \in L_2,\quad w\in L_1
• N : \rho\left(w\right) \notin L_2,\quad w\notin L_1

Les problèmes suivants sont indécidables avec des MT :

• a) Etant donnée M une MT et \omega\in\Sigma^*, est-ce que M s'arrête avec \omega en entrée?
• b) Etant donnée M une MT, est-ce que M s'arrête avec le mot vide en entrée?
• c) Etant donnée M une MT, est-ce que M s'arrête avec certains mots en entrée? (existe-il des entrées avec lesquelles la machine s'arrête?)
• d) Etant donnée M une MT,, est-ce que M s'arrête quelque soit le mot en entrée?
• e) Etant donnée M₁ et M₂ deux MT, est-ce qu'elles s'arrêtent pour les mêmes entrées?
• f) Etant donnée M une MT qui semi-décide L, est-ce que L est rationnel? (resp. algébrique? récursif?)
• g) Il existe une MT M pour laquelle le problème suivant est indécidable : “Etant donné \omega\in\Sigma^* , est que M s'arrête avec \omega en entrée?

C'est le “halting problem” dont l'indécidabilité a été vu la dernière fois.

On fait une réduction \rho ramenant le halting problem à ce problème.

Soit w =a_1 a_2 a_3 \ldots a_m. Ecrire le mot sur le ruban par une suite de mouvements et écritures : R a_1 R a_2 R a_3 \ldots R a_m L_{\sqcup} avec une machine qui prend w \in \Sigma^* et produit cette séquence \in \Sigma_U^*. Le codage ce cette machine – fonction récursive – est laissé en exercice.

Ensuite, \rho : \Sigma_U \rightarrow \Sigma_U,

\rho est récursive (pas triviale à démontrer).

On fait une réduction de problème (b) au problème ©. "M" \mapsto \underbrace{"Efface\quad M"}_{M\prime}. Efface est une MT qui efface le ruban. Mi s'arrete pour une ou des entrées si et seulement si M s'arrête avec le mot vide en entrée. Donc le problème © est indécidable.

Comme dans (3), même réduction. Si et seulement si M' s'arrête pour toutes ses entrées…

Soit M une machine de Turing, et w\in \Sigma^*. On construit M', la MT équivalente à la MT à 2 rubans qui réalise l'algorithme suivant :

1. on déplace le contenu du ruban 1 sur le ruban 2.
2. on fait fonctionner M sur le ruban 1. Si M s'arrête, on fait:
3. …fonctionner U sur le ruban 2.

M \mapsto M\prime est récursif. \rho_f: M' s'arrête avec w en entrée ⇔ M s'arrête avec le mot vide en entrée et U s'arrête avec w en entrée.

• L(M') = \Phi : M ne s'arrête pas avec le mot vide (ou w \in H).
• L(M') = H : si M s'arrête avec le mot vide.
• \Phi est rationnel (régulier), algébrique (hor sontexte) et récursif.
• H : aucun des trois.
• \rho_f fait une réduction du problème (b) au problème (f), avec des variantes.

U ?

Etant donnée une MT M, un état q de M et un mot w\in \Sigma^*, est-ce que M passe par l'état q avec w en entrée?

• Est-ce que ce problème est décidable ou indécidable?
• Indécidable, car il suffit de considérer q\in H
  1. On peut ramener de manière récursive tout MT à une MT à 1 suel état d'arrêt h
  2. Pour cette MT M', il suffit de prendre q = h pour résoudre le halting problem.

Soit M une MT et k\in \mathbb{N} et w\in \Sigma^*. On dit que M utilise (au moins) k cases du ruban avec le mot w en entrée ⇔

Etant donnée une MT, M, un mot w\in \Sigma^* et k\in \mathbb{N} est-ce que M utilise au moins k cases avec le mot w en entrée?

• Décidable ou indécidable?
• Décidable !

| K | \times |\Sigma|^{k-1} peut être très grand, mais fini ⇒ on peut détecter des boucles éventuelles.

suite de l'explication à rajouter

Soit M une MT, w\in \Sigma^* et f:\Sigma^* \rightarrow \mathbb{N} une fonction récursive. Est-ce que M utilise au moins f(w) cases avec w en entrée?

• Décidable : comme pour le cas précédent, mais avec une phase d'initialisation pour “calculer k” = f(w).

Soit M un MT, w\in \Sigma^*. Est-ce qu'il existe un entier k \geq O tel que M utilise moins de k cases avec w en entrée?

• Indécidable. exercice.

II. Indécidabilité ←→ II.5 Problèmes indécidables pour les grammaires