Calculabilité et décidabilité

Supposons qu'un tel décideur existe : une fonction arrete p x qui s'arrête toujours et renvoie true ssi le programme p appliqué à l'entrée x s'arrête. Construisons alors :

let diagonale p =
  if arrete p p then (while true do () done)   (* boucle pour toujours *)
  else ()                                       (* s'arrête *)

diagonale prend un programme p ; elle boucle si p s'arrête sur lui-même, et s'arrête sinon. Appliquons diagonale à elle-même :

• si diagonale diagonale s'arrête, alors arrete diagonale diagonale vaut true, donc diagonale boucle — contradiction ;
• si elle ne s'arrête pas, alors arrete vaut false, donc diagonale s'arrête — contradiction.

Dans les deux cas, contradiction. L'hypothèse est fausse : arrete ne peut pas exister. $\square$

(a) Décidable : n mod 2 = 0, qui s'arrête toujours. (b) Décidable : un parcours du tableau (fini) s'arrête toujours. (c) Indécidable : c'est un cas particulier du problème de l'arrêt — décider l'arrêt sur l'entrée 0 pour tout p permettrait… de décider l'arrêt.

let rec tous_positifs l =
  match l with
  | [] -> true
  | x :: reste -> x > 0 && tous_positifs reste

La récursion porte sur une liste strictement plus courte à chaque appel : elle atteint [] en un nombre fini d'étapes (variant : la longueur). La fonction s'arrête sur toute entrée et donne la bonne réponse : le problème est décidable.

Si p s'arrête, on le constate au bout d'un temps fini (réponse oui). Mais si p boucle, l'observation ne se termine jamais : on ne pourra jamais répondre non avec certitude — peut-être s'arrêtera-t-il à l'étape suivante ? On obtient un semi-décideur (correct sur les oui), pas un décideur. C'est précisément cette asymétrie qui rend l'arrêt non décidable.

(* execute_n_etapes p x k : exécute p sur x pendant au plus k étapes,
   renvoie true si p s'est arrêté dans ce délai (fonction idéalisée). *)
let semi_arrete p x =
  let k = ref 0 in
  while not (execute_n_etapes p x !k) do k := !k + 1 done;
  true

On simule p de plus en plus longtemps. Si p s'arrête (en k0 étapes), on le détecte dès k = k0 et l'on renvoie true. Mais si p boucle, la recherche sur k ne s'arrête jamais : aucune réponse non. Semi-décideur, pas décideur.

Pour Syracuse, on ignore si la boucle s'arrête pour tout n (conjecture ouverte), faute d'un variant connu — mais c'est une question sur un programme précis. L'indécidabilité de l'arrêt est plus forte : elle affirme qu'aucun algorithme ne peut répondre pour tous les programmes. On peut très bien prouver la terminaison de tel programme donné (par un variant) ; ce qu'on ne peut pas, c'est un procédé général valable pour tous.

Supposons un décideur arrete_partout. Pour décider si un programme q s'arrête sur une entrée y, construisons le programme r qui, sur n'importe quelle entrée, exécute q sur y (en ignorant son argument). Alors r s'arrête sur toutes les entrées si et seulement si q s'arrête sur y. Si arrete_partout r existait, on déciderait l'arrêt de q sur y — impossible. Donc « s'arrêter partout » est indécidable.

let diagonale p =
  if arrete p p then (while true do () done) else ()

Notons $D$ le programme diagonale. Que fait diagonale D ? Par définition, elle teste arrete D D.

• Cas arrete D D = true : cela signifie « $D$ appliqué à $D$ s'arrête ». Or, dans ce cas, diagonale D entre dans while true : elle ne s'arrête pas. Contradiction avec true.
• Cas arrete D D = false : « $D$ appliqué à $D$ ne s'arrête pas ». Or diagonale D prend alors la branche else et s'arrête. Contradiction avec false.

arrete ne peut donc renvoyer ni true ni false de façon cohérente : elle ne peut exister.

Réduction depuis l'arrêt. Pour décider si q s'arrête sur y, construisons p qui : exécute q sur y, puis (s'il revient) affiche 42. Alors p affiche 42 si et seulement si q s'arrête sur y. Un décideur de « affiche 42 » donnerait donc un décideur de l'arrêt : impossible. C'est une illustration du théorème de Rice — toute propriété non triviale du comportement est indécidable.

Si l'on savait calculer castor n, on déciderait l'arrêt : pour savoir si un programme p de taille n s'arrête, il suffirait de le simuler castor n étapes ; s'il ne s'est pas arrêté dans ce délai maximal, c'est qu'il ne s'arrêtera jamais. Or l'arrêt est indécidable ; donc castor n'est pas calculable. Cette fonction croît plus vite que toute fonction calculable : un exemple concret de l'au-delà du calculable.

(a) Semi-décidable non décidable : on simule, on confirme les oui (arrêt), jamais les non. (b) Non semi-décidable : c'est le complémentaire de (a) ; si (a) et (b) étaient toutes deux semi-décidables, l'arrêt serait décidable (lancer les deux semi-décideurs en parallèle) — impossible. (c) Décidable : il n'y a que $2^n$ valuations à essayer (chapitre 17), l'énumération s'arrête toujours (même si elle est exponentielle). Décidabilité et efficacité sont deux questions distinctes : un problème peut être décidable mais coûteux.