Chapitre 15 : Calculabilité, décidabilité.

1. Tout programme peut être une donnée

Tout programme peut être vu comme une donnée :

• On peut le stocker dans un fichier.
• Un compilateur, comme un interprète, est lui-même un programme : il prend en entrée le texte d'un autre programme, qu'il traite donc comme une donnée.
• Un système d'exploitation est un programme qui manipule d'autres programmes.

Cette précision est là pour bien mettre en avant que de nos jours un algorithme est programmable et n'est donc pas induit dans la conception de la machine elle-même. On fait ainsi la différence, par exemple, entre une horloge mécanique et une montre programmée informatiquement.

2. Machine de Turing

Une machine de Turing est une machine conceptualisée par Alan Turing. C'est une machine imaginaire que l'on peut représenter ainsi :

• Cette machine dispose d'un ruban infini, découpé en cases contenant chacune un symbole (par exemple 0, 1, ou le symbole « vide »). Les symboles utilisables sont en nombre fini.
• Cette machine dispose d'une tête de lecture et d'écriture, placée sur une case du ruban.
• À tout instant, la machine se trouve dans un état, choisi parmi un nombre fini d'états possibles (par exemple 0, 1 ou 2). L'état est une caractéristique de la machine, et non de la tête de lecture : c'est ce qu'elle « retient » de ce qu'elle a déjà fait.
• La tête de lecture peut se déplacer d'une case vers la gauche ou vers la droite.
• La machine dispose d'une table de transition. Elle indique, pour chaque couple (état de la machine, symbole lu sur le ruban), le symbole à écrire, le déplacement à effectuer et le nouvel état.

8. Thèse de Church-Turing

Dans les années 1930, les travaux des mathématiciens Alonzo Church et Alan Turing ont permis d'éclaircir ce qu'est un programme basé sur des calculs.

Chacun a proposé sa propre définition de ce que veut dire « calculer » : le lambda-calcul pour Church, la machine de Turing (vue ci-dessus) pour Turing. On a ensuite démontré que ces deux définitions, pourtant très différentes, décrivent exactement les mêmes fonctions calculables. Ce constat a conduit à la thèse suivante :

Tout traitement réalisable mécaniquement peut être accompli par une machine de Turing.

Attention : il s'agit bien d'une thèse et non d'un théorème. On ne peut pas la démontrer, car elle relie une notion intuitive (« ce qu'un humain ou une machine peut calculer en suivant une méthode mécanique ») à une définition mathématique précise (la machine de Turing). Elle n'a jamais été mise en défaut : tous les modèles de calcul proposés depuis, y compris nos ordinateurs actuels, calculent exactement les mêmes fonctions qu'une machine de Turing.

9. La calculabilité en informatique

Définition

En informatique, la calculabilité étudie ce qu’un ordinateur peut ou ne peut pas résoudre à l’aide d’un programme.

Problème calculable

Un problème est dit calculable s’il existe un algorithme qui fournit une réponse correcte et qui termine (s'arrête au bout d'un nombre fini d'étapes) pour toute entrée possible.

Problème non calculable

Un problème est dit non calculable lorsqu’aucun algorithme ne peut le résoudre dans tous les cas possibles.

Limites de l’informatique

La calculabilité ne dépend ni de la puissance de l’ordinateur, ni du langage de programmation utilisé : un problème non calculable le reste quelle que soit la machine. Il s'agit d'une limite théorique, et non d'un manque de moyens techniques.

11. La décidabilité en informatique

Définition

En informatique, un problème est dit décidable s’il existe un algorithme qui donne une réponse oui ou non pour toutes les entrées possibles, et qui se termine toujours.

Problème décidable

Un problème est décidable lorsqu’un algorithme permet de répondre correctement dans tous les cas, sans jamais boucler indéfiniment.

Problème indécidable

Un problème est indécidable lorsqu’aucun algorithme ne peut répondre correctement pour toutes les entrées tout en garantissant de toujours s’arrêter.

Lien avec la calculabilité

La décidabilité est le cas particulier de la calculabilité appliqué aux problèmes à réponse oui / non. Pour un tel problème, être décidable et être calculable sont donc la même chose.

La calculabilité est la notion la plus large : elle concerne aussi des problèmes dont la réponse n'est pas un oui ou un non, comme trier une liste ou calculer un PGCD.

Exemple célèbre

Le problème de l’arrêt consiste à savoir si un programme s’arrêtera ou non pour une entrée donnée. C'est un problème à réponse oui / non. Nous allons démontrer dans la partie suivante qu'il est indécidable : aucun algorithme ne peut toujours donner la bonne réponse.

12. Le problème de l'arrêt

On peut se demander s'il est possible de prévoir qu'un algorithme s'arrêtera.

Est-il possible d'écrire un algorithme permettant de savoir si n'importe quel autre algorithme s'arrête ou non ?

Raisonnons par l'absurde :

Imaginons que ce programme, que l'on appellera \(A\), existe.

On lui donne deux choses : un programme \(P\) et l'entrée \(e\) sur laquelle on veut l'exécuter. Alors \(A(P,e)=VRAI\) si \(P\) s'arrête sur l'entrée \(e\), et \(A(P,e)=FAUX\) si \(P\) ne s'arrête pas sur cette entrée.

Rappelons-nous qu'un programme est une donnée (partie 1) : on peut donc donner un programme à lui-même comme entrée.

Que se passe-t-il si le texte reçu n'a pas de sens pour \(P\) ? \(P\) peut planter : une erreur compte comme un arrêt. Il peut aussi ignorer son entrée, ou boucler. Dans tous les cas, soit il s'arrête, soit il ne s'arrête pas : \(A(P,P)\) a donc bien une réponse, VRAI ou FAUX, pour tout programme \(P\).

Construisons maintenant un programme \(B\) défini de la manière suivante :

1. Il prend un programme \(P\) en entrée, puis évalue \(A(P,P)\).
2. Si \(A(P,P)\) est VRAI, il lance une boucle infinie.
3. Si \(A(P,P)\) est FAUX, il s'arrête.

Appliquons enfin \(B\) à lui-même et regardons \(B(B)\) :

• Si \(B(B)\) s'arrête, c'est que \(A(B,B)\) valait FAUX, c'est-à-dire que \(B\) ne s'arrête pas sur l'entrée \(B\) : contradiction.
• Si \(B(B)\) ne s'arrête pas, c'est que \(A(B,B)\) valait VRAI, c'est-à-dire que \(B\) s'arrête sur l'entrée \(B\) : contradiction également.

Les deux cas sont impossibles, donc le programme \(B\) ne peut pas exister. Or, si \(A\) existait, il suffirait de quelques lignes pour construire \(B\) à partir de lui. C'est donc que \(A\) n'existe pas : le problème de l'arrêt est indécidable.

14. La terminaison d’un algorithme

Le problème de l'arrêt montre qu'aucun programme ne pourra jamais décider à notre place si n'importe quel algorithme s'arrête. Pour un algorithme donné, on peut en revanche souvent le prouver à la main : c'est l'objet de cette partie.

Définition

Un algorithme est dit terminant s’il s’arrête après un nombre fini d’étapes, quelle que soit l’entrée fournie.

Pourquoi la terminaison est importante

Un algorithme qui ne termine pas ne donne jamais de résultat. Avant de se demander si le résultat est le bon (partie suivante), il faut donc s'assurer que l'algorithme termine.

Causes fréquentes de non-termination

• une boucle dont la condition ne devient jamais fausse,
• une variable de boucle qui n’évolue pas correctement,
• une récursion sans condition d’arrêt.

Principe de preuve de terminaison

Pour prouver qu’un algorithme termine, on montre qu’à chaque étape une quantité diminue strictement et qu’elle ne peut pas diminuer indéfiniment.

Exemple simple

def compte_a_rebours(n):
    while n > 0:
        n = n - 1

Ici, la quantité qui décroît (on l'appelle le variant de la boucle) est la variable n : c'est un entier qui diminue strictement à chaque tour, et la condition n > 0 garantit qu'il reste positif tant que la boucle tourne. Une suite d'entiers positifs strictement décroissante ne peut pas être infinie : la boucle termine donc forcément.

def mystere(n):
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = n + 1
    return n

16. Prouver la correction d’un algorithme

Qu’est-ce que la correction d’un algorithme ?

Un algorithme est dit correct s’il produit toujours le résultat attendu pour toutes les entrées valides.

Objectif d’une preuve de correction

Prouver la correction d’un algorithme consiste à montrer, de manière logique et rigoureuse, que l’algorithme fait exactement ce qui est demandé dans l’énoncé.

Deux aspects de la correction

• Correction partielle : si l’algorithme termine, alors le résultat est correct.
• Correction totale : l’algorithme termine et le résultat est correct.

La correction totale s'obtient donc en ajoutant à la correction partielle une preuve de terminaison (partie précédente).

Rôle des invariants

Pour les algorithmes utilisant des boucles, on utilise souvent un invariant de boucle.

Un invariant est une propriété qui est vraie :

• avant l’entrée dans la boucle,
• après chaque itération,
• à la fin de la boucle.

🛠 Méthode générale de preuve

• Décrire précisément ce que l’algorithme doit faire.
• Identifier les hypothèses sur les données d’entrée.
• Montrer que chaque étape respecte l’objectif.
• Conclure que le résultat final est correct.

Exemple simple

Algorithme : calculer la somme des éléments d’une liste.

somme = 0
pour chaque element de la liste :
    somme = somme + element

Invariant : après chaque itération, somme est égale à la somme des éléments déjà parcourus.

À la fin de la boucle, tous les éléments ont été parcourus, donc somme est bien la somme totale.

def maximum(liste):
    max_val = liste[0]
    for x in liste:
        if x > max_val:
            max_val = x
    return max_val