Théorème 4Calculabilité

Indécidabilité du problème de l'arrêt

On pose $K = \{e \in {\mathbb N} : \varphi_e(e)\!\downarrow\}$ , l'ensemble des indices des programmes qui s'arrêtent sur leur propre indice, et $H = \{(e, x) : \varphi_e(x)\!\downarrow\}.$ Décider si $(e, x) \in H$ , c'est le problème de l'arrêt.

Énoncé

(i) Les ensembles $K$ et $H$ sont récursivement énumérables.

(ii) L'ensemble $K$ n'est pas récursif, et $H$ non plus : le problème de l'arrêt est indécidable.

(iii) Le complémentaire $\mathbb N \setminus K$ n'est pas récursivement énumérable.

Démonstration

(i) Par la forme normale (Kleene), $e \in K \iff \exists t\, T_1(e, e, t)$ et $(e, x) \in H \iff \exists t\, T_1(e, x, t)$ , relations primitives récursives sous le quantificateur.

(ii) Supposons $K$ récursif. La fonction $g(e) \simeq \mu y\, \big[\chi_K(e) = 0\big]$ est récursive ; elle vaut $0$ si $e \notin K$ , et n'est pas définie si $e \in K$ . Par le point (i) de Kleene, elle a un indice $d$ : $g = \varphi_d$ . Alors $\begin{aligned} d \in K &\iff \varphi_d(d)\!\downarrow \\ &\iff g(d)\!\downarrow \iff d \notin K, \end{aligned}$ ce qui est absurde.

Si $H$ était récursif, $K$ , image réciproque de $H$ par $e \mapsto (e, e)$ , le serait aussi (Récursif, r.e., (iii)).

(iii) Si $\mathbb N \setminus K$ était récursivement énumérable, $K$ serait récursif par le point (ii) de Récursif, r.e., puisqu'il l'est par (i).

Le tableau des calculs de

P_e

sur

x

pour

e, x \leqslant 11

, obtenus en décodant

e

: un point vert quand le calcul s'arrête, une croix grise quand une configuration se répète, ce qui prouve qu'il boucle ; seul

P_{11} = \mathrm{DEC}(1, 0)

change de comportement selon

x

. La fonction

g

de la preuve, en rouge, fait le contraire de chaque ligne sur la diagonale : elle ne peut être aucune des lignes du tableau complet.

□

Remarque

La preuve est la diagonale de Cantor (Théorème de Cantor) appliquée au tableau infini des $\varphi_e(x)$ : $g$ diffère de la ligne $e$ en sa case diagonale. Ce n'est pas l'existence de $g$ qui pose problème, puisque c'est une fonction, mais sa calculabilité, qui viendrait de celle de $K$ .

Remarque

Turing a établi en 1936 l'indécidabilité d'un problème voisin, savoir si une machine imprime indéfiniment des chiffres ; la formulation en termes d'arrêt est postérieure. L'énoncé ne dit pas qu'on ignore si tel programme s'arrête, mais qu'aucun programme ne répond à cette question pour tous les programmes à la fois.

Repose sur

Forme normale de Kleene et fonction universelle Ensembles récursifs et récursivement énumérables

Sert à

Théorème de Rice Calculabilité et incomplétude