Problème — 1936, ou ce qu'aucune machine ne pourra faire

Application directe du cours · niveau 3 (difficile) · NSI (terminale), chapitre 15 — Histoire de l'informatique

Énoncé

Problème — 1936, ou ce qu'aucune machine ne pourra faire.

L'année qui invente l'ordinateur est aussi celle qui en fixe les limites. On reconstitue ici le raisonnement de Turing, en Python.

Un professeur propose d'écrire une fonction s_arrete(source, entree) qui renverrait True si le programme dont le texte est source s'arrête sur l'entrée entree, et False s'il boucle indéfiniment. Elle devrait, elle-même, toujours s'arrêter et toujours répondre juste.


def paradoxe(source):
    if s_arrete(source, source):
        while True:        # si on repond "il s'arrete", on boucle
            pass
    else:
        return "fini"      # si on repond "il boucle", on s'arrete

À quoi une telle fonction servirait-elle concrètement ?
On suppose qu'elle existe. Montrer que le programme ci-dessus conduit à une contradiction.
Que conclut-on ? Quel est le nom de ce résultat, et de qui date-t-il ?
Quelles conséquences pratiques a-t-il sur le travail du programmeur ?

Corrigé

1. À quoi elle servirait. À détecter automatiquement toute boucle infinie avant exécution : plus aucun programme ne se figerait, un système d'exploitation pourrait refuser de lancer un processus qui ne terminera pas, et un professeur pourrait corriger les copies sans les exécuter. C'est précisément parce que ce serait si utile qu'il faut savoir que c'est impossible.

2. La contradiction. Appliquons paradoxe à son propre texte source, noté $P$ .

Si paradoxe(P) s'arrête : c'est que le test a renvoyé False, donc que ce même appel ne s'arrête pas. Contradiction.
Si paradoxe(P) ne s'arrête pas : c'est qu'on est entré dans la boucle, donc que le test a renvoyé True, donc que cet appel s'arrête. Contradiction encore.

Les deux cas sont impossibles, et le reste du programme est parfaitement licite : c'est donc l'hypothèse de départ qui est fausse.

3. La conclusion. La fonction s_arrete ne peut pas exister. C'est l'indécidabilité du problème de l'arrêt, démontrée par Alan Turing en 1936, dans l'article même où il définit la machine universelle ; Alonzo Church avait obtenu la même année un résultat équivalent par le lambda-calcul. Remarquons la date : on démontre ce qu'aucun ordinateur ne pourra faire douze ans avant d'en construire un.

4. Conséquences pratiques.

La terminaison d'une fonction récursive doit être prouvée à la main, en exhibant un variant qui décroît strictement vers le cas de base : aucun outil ne le fera à notre place dans tous les cas.
Les analyseurs de code sont nécessairement imparfaits : ils signalent de fausses alertes, ou laissent passer de vrais défauts. Ce n'est pas une faiblesse de programmation, c'est une limite mathématique.
Le test garde donc toute sa place : on ne peut pas remplacer l'essai par une preuve automatique universelle. Tester ne prouve pas l'absence de défaut, mais c'est souvent tout ce dont on dispose.

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.