Décidable ou non ? — exercice corrigé de NSI (terminale) (chapitre 16)

Décidable ou non ?

Calculabilité, décidabilité et paradigmes de programmation · niveau 3 (difficile)

Énoncé

Décidable ou non ?

Pour chacune des questions suivantes, dire si le problème de décision est décidable, et justifier en une phrase.

Ce tableau d'entiers est-il trié par ordre croissant ?
Ce programme Python contient-il le mot-clé while ?
Ce programme Python s'arrête-t-il sur l'entrée 0 ?
Ce programme Python, qui ne contient ni boucle ni appel récursif, s'arrête-t-il ?
Ces deux programmes calculent-ils la même fonction ?

Corrigé

Décidable : un parcours compare chaque élément à son suivant, et s'arrête toujours, en $O (n)$ .
Décidable : c'est une question sur le texte du programme, pas sur son exécution ; une recherche de motif dans une chaîne suffit — Boyer--Moore ferait l'affaire.
Indécidable : c'est le problème de l'arrêt, restreint à une entrée fixée ; la démonstration du cours s'y applique telle quelle.
Décidable : sans boucle ni récursion, le nombre d'instructions exécutées est majoré par la taille du programme, donc il s'arrête ; et l'absence de boucle se vérifie mécaniquement. C'est un exemple de sous-classe décidable.
Indécidable : si on savait le décider, on saurait comparer un programme quelconque à un programme trivial et en déduire son comportement, donc résoudre l'arrêt.

La leçon : les questions portant sur le texte d'un programme sont en général décidables, celles qui portent sur son comportement à l'exécution ne le sont en général pas.