L'arrêt sur l'entrée vide

On réduit arrêt à arrêt-vide — dans ce sens, puisque l'on veut transporter la difficulté de arrêt vers arrêt-vide.

La transformation. À un couple $(p,x)$, on associe le texte du programme

(* q ignore son entree, se donne x, et lance p dessus. *)
let q () =
  let x = "..." in          (* la chaine x, ECRITE EN DUR dans le texte de q *)
  executer p x

Fabriquer ce texte est un simple travail de chaîne de caractères : on colle $x$ et $p$ dans un patron. C'est calculable, et en temps linéaire en $|p|+|x|$ — donc polynomial, ce qui est bien plus que nécessaire ici.

L'équivalence. Par construction, $q$ ne fait rien d'autre que lancer $p$ sur $x$. Donc

$$q\text{ s’arreˆte sur l’entreˊe vide}⟺p\text{ s’arreˆte sur }x.$$

La conclusion. Supposons arrêt-vide décidable par un programme $D$. Alors le programme suivant déciderait arrêt : recevant $(p,x)$, il fabrique le texte de $q$, appelle $D$ sur ce texte, et rend sa réponse. Or arrêt est indécidable. Contradiction : $D$ n'existe pas.

Ce que la démonstration illustre. On n'a pas refait de diagonale — on a réutilisé l'indécidabilité de arrêt. C'est le même mouvement que la np-difficulté à partir de sat : un premier résultat difficile, obtenu par un argument propre (la diagonale pour arrêt, Cook-Levin pour sat), puis une cascade de réductions.

Et un point de vocabulaire. La réduction employée ici transporte l'indécidabilité et n'a pas besoin d'être polynomiale — seulement calculable. C'est la même idée, à une exigence de ressources près : pour la complexité on borne le coût de la traduction, pour la calculabilité on ne le borne pas.