Décidable ou non ?
Exercice de TD · niveau 3 (difficile) · NSI (terminale), chapitre 16 — Calculabilité, décidabilité et paradigmes de programmation
É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 .
- 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.
Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.