Calculabilité - Décidabilité

1. Un programme est une donnée

1.1. Un programme prend des données en entrée

Les codes que nous manipulons ressemblent souvent à cela :

def accueil(n):
    for k in range(n):
        print("bonjour")

Le programme accueil a besoin d’un paramètre pour fonctionner : ici un nombre entier n. Voici comment représenter notre machine accueil, son paramètre d’entrée (par exemple 5) et sa sortie (les cinq « bonjour ») :

1.2. … mais un programme est lui aussi une donnée

Le code de accueil est avant tout un fichier texte, par exemple accueil.py. Pour l’exécuter, on tape dans un terminal :

python3 accueil.py

Le programme utilisé est ici python3, qui prend comme paramètre le programme accueil.py. Ce paramètre accueil.py est un ensemble de caractères, qui contient les instructions que python3 va interpréter. L’illustration correspondante est donc :

On peut même aller plus loin : l’instruction python3 accueil.py est tapée dans un Terminal, qui est lui-même un programme :

1.3. Conclusion

Il n’y a aucun obstacle à considérer un programme comme une simple donnée, pouvant être reçue en paramètre par un autre programme (voire par lui-même !).

C’est le fondement :

• de l’interprétation (Python, JavaScript…) et de la compilation (C, Rust…) ;
• du raisonnement qui va suivre sur les limites du calcul.

À titre anecdotique, on pourra exécuter avec intérêt cette instruction :

a='a=%r;print(a%%a)';print(a%a)

Ce type de code (magique !) existe dans tous les langages et s’appelle un quine : un programme dont la sortie est son propre code source.

2. Le problème de l’arrêt

2.1. Un programme s’arrête-t-il ?

Considérons le programme suivant :

def countdown(n):
    while n != 0:
        print(n)
        n = n - 1
    print("fini")

En l’observant attentivement, on peut prévoir que countdown(10) affichera les nombres de 10 à 1 avant d’écrire « fini ». Puis le programme s’arrêtera.

Que va provoquer countdown(10.8) ? Comme la variable n ne sera jamais égale à 0, le programme va rentrer dans une boucle infinie, il ne s’arrêtera jamais. Nous avons pu prévoir ceci en regardant attentivement le code, en « remarquant » qu’une variable n non entière provoquerait une boucle infinie.

Question : est-ce qu’un programme d’analyse de programmes aurait pu faire cela à notre place ?

2.2. Supposons qu’il existe : la fonction halt

Un programme est une suite d’instructions (le code source) et peut, comme on vient de le voir, être le paramètre d’entrée d’un autre programme qui l’analyserait. Imaginons un tel programme magique, que nous appellerons halt. Il prendrait en entrée :

• un paramètre prog (le code source du programme à analyser) ;
• un paramètre x (le paramètre d’entrée de prog).

L’instruction halt(prog, x) renverrait :

• True si prog(x) s’arrête ;
• False si prog(x) ne s’arrête pas.

Exemples attendus :

• halt(countdown, 10) renverrait True ;
• halt(countdown, 10.8) renverrait False.

Pour montrer que halt ne peut pas exister, nous allons supposer qu’elle existe… et aboutir à une contradiction.

2.3. Le piège : la fonction sym

Construisons un programme sym qui prend un programme en entrée et fait systématiquement l’inverse de ce que halt prédit :

def sym(prog):
    if halt(prog, prog) == True:
        while True:        # boucle infinie
            pass
    else:
        return 1           # s'arrête

Le programme halt est appelé avec les paramètres prog, prog, ce qui signifie que prog se prend lui-même en paramètre. Ce n’est pas choquant : un code source est une donnée comme une autre.

Le programme sym reçoit donc en paramètre un programme prog, et :

• rentre dans une boucle infinie si prog(prog) s’arrête ;
• renvoie 1 si prog(prog) ne s’arrête pas.

Autrement dit, sym fait systématiquement le contraire de ce que halt prédit.

2.4. La contradiction : sym(sym)

Puisqu’un programme peut prendre en paramètre son propre code source, que donnerait l’appel à sym(sym) ?

Deux cas peuvent se présenter, suivant ce que renvoie halt(sym, sym).

• Cas 1 : halt(sym, sym) renvoie True, ce qui signifie que sym(sym) devrait s’arrêter. Mais dans ce cas, l’exécution de sym(sym) rentre dans la boucle infinie. Contradiction.
• Cas 2 : halt(sym, sym) renvoie False, ce qui signifie que sym(sym) devrait boucler indéfiniment. Mais dans ce cas, l’exécution de sym(sym) se termine correctement et renvoie la valeur 1. Contradiction.

Dans les deux cas, on aboutit à une absurdité : notre programme halt ne peut pas exister.

2.5. Le théorème de l’arrêt

Nous venons de prouver que halt, censé prédire si un programme prog s’arrête sur une entrée x, ne peut pas exister. Ce résultat théorique, d’une importance cruciale, s’appelle le théorème de l’arrêt (ou théorème d’indécidabilité de l’arrêt).

Il a été démontré par Alan Turing en 1936, dans un article intitulé « On computable numbers, with an application to the Entscheidungsproblem ».

Pour sa démonstration, Turing présente un modèle théorique de machine capable d’exécuter des instructions basiques sur un ruban infini : les machines de Turing .

À la même époque, le mathématicien Alonzo Church démontre lui aussi ce théorème, par un moyen totalement différent, en inventant le lambda-calcul .

Tous deux mettent ainsi un terme au rêve du mathématicien allemand David Hilbert , qui avait posé en 1928 la question de l’existence d’un algorithme capable de répondre « oui » ou « non » à n’importe quel énoncé mathématique posé sous forme décisionnelle (« un triangle rectangle peut-il être isocèle ? », « existe-t-il un nombre premier pair ? »).

Cette question, appelée problème de la décision ou Entscheidungsproblem en allemand, est définitivement tranchée par le problème de l’arrêt : un tel algorithme ne peut pas exister, puisque, par exemple, aucun algorithme ne peut répondre « oui » ou « non » à la question « ce programme va-t-il s’arrêter ? ».

3. Le théorème de Rice

3.1. Énoncé

Le théorème de l’arrêt est étendu plus tard par le théorème de Rice (1953) :

Toute question sémantique non triviale portant sur ce que fait un programme est indécidable.

Autrement dit : aucun algorithme ne peut, en analysant le code source d’un programme, répondre à coup sûr à une question portant sur son comportement. Henry Gordon Rice démontre que toutes ces questions peuvent être ramenées (on dit réduites) au problème de l’arrêt, qui est indécidable.

3.2. Exemples de questions indécidables

• « Ce programme va-t-il s’arrêter ? » (le problème de l’arrêt) ;
• « Ce programme va-t-il renvoyer la valeur 12 ? » ;
• « Ce programme va-t-il un jour renvoyer un message d’erreur ? » ;
• « Deux programmes calculent-ils la même fonction ? »

Conséquence pratique : un analyseur statique parfait, qui détecterait toutes les boucles infinies, tous les bugs et toutes les failles de sécurité, est mathématiquement impossible. Les outils réels (linters, vérificateurs de types) ne donnent que des approximations : ils détectent une partie des erreurs, mais jamais toutes.

4. Calculabilité

4.1. Fonction calculable

Le problème de l’arrêt est dit indécidable car la fonction qui le résout (notre programme halt) n’est pas calculable. Mais que recouvre exactement cette notion ?

Opérations élémentaires

Le calcul mathématique peut se réduire à une succession d’opérations élémentaires. Une opération élémentaire est une opération si simple qu’elle ne nécessite aucune décomposition pour être exécutée :

• ajouter 1 à un nombre, comparer deux nombres ;
• lire ou écrire un caractère sur un support ;
• choisir entre deux instructions selon le résultat d’une comparaison.

La multiplication entière, par exemple, n’est pas une opération élémentaire : elle s’obtient par additions successives. De même, la factorielle s’obtient par multiplications successives. Toute fonction « calculable » se ramène, in fine, à une suite finie d’opérations élémentaires.

Définition

Une fonction \(f\) est calculable s’il existe un algorithme (autrement dit, un programme) qui, à partir de chaque entrée \(x\), produit en temps fini la sortie \(f(x)\) attendue.

Quelques exemples de fonctions calculables :

• \(f(n) = n!\), la factorielle ;
• \(f(n) = \) le \(n\)-ième chiffre de \(\pi\) ;
• \(f(L) = L\) triée par ordre croissant.

Et un exemple de fonction non calculable : la fonction halt, qui répondrait à la question de l’arrêt. Elle n’est pas calculable, comme le démontre le théorème de Turing.

Une infinité de fonctions non calculables

Un résultat surprenant : la plupart des fonctions de \(\mathbb{N}\) dans \(\mathbb{N}\) ne sont pas calculables.

Pourquoi ? Un programme est une suite finie de caractères : l’ensemble des programmes possibles est donc dénombrable (on peut, en théorie, les énumérer). Mais l’ensemble des fonctions de \(\mathbb{N}\) dans \(\mathbb{N}\) est, lui, non dénombrable (argument diagonal de Cantor). Comme il y a strictement plus de fonctions que de programmes, il existe nécessairement des fonctions qu’aucun programme ne peut calculer.

La calculabilité est donc l’exception, pas la règle. Mais en pratique, toutes les fonctions « utiles » que nous écrivons en NSI sont calculables : c’est la définition même d’un algorithme.

4.2. La machine de Turing

Pour formaliser ce qu’est un « algorithme », Alan Turing propose en 1936 un modèle théorique de machine extrêmement simple, mais d’une puissance d’expression universelle.

Description

Une machine de Turing est composée de :

• un ruban infini divisé en cases, chacune contenant un symbole (par exemple 0, 1 ou un blanc) ;
• une tête de lecture/écriture positionnée sur une case, capable de lire le symbole, d’écrire un nouveau symbole, et de se déplacer d’une case à gauche ou à droite ;
• un état courant, choisi parmi un ensemble fini d’états ;
• une table de transitions qui, en fonction de l’état courant et du symbole lu, indique : le symbole à écrire, le déplacement à effectuer (gauche, droite, ou aucun) et le nouvel état à adopter.

L’exécution s’arrête lorsque la machine atteint un état dit final (acceptation ou rejet). Aussi rudimentaire que cela paraisse, ce dispositif est capable d’exécuter n’importe quel algorithme.

Machine de Turing universelle

Le coup de génie de Turing est d’avoir montré qu’il existe une machine de Turing universelle : une machine dont la table de transitions est fixée une fois pour toutes, et qui peut simuler n’importe quelle autre machine de Turing dont la description est inscrite sur son ruban.

C’est exactement ce que fait un ordinateur : le processeur est une machine universelle, qui exécute des programmes (eux-mêmes encodés comme des données en mémoire). On retrouve ici l’idée fondatrice de la section 1 : un programme est une donnée comme une autre.

4.3. Thèse de Church-Turing

Turing a proposé d’identifier l’ensemble des fonctions calculables (au sens des opérations élémentaires) à l’ensemble des fonctions programmables sur une machine de Turing. C’est la thèse de Church-Turing :

Les fonctions calculables sont exactement les fonctions programmables sur une machine de Turing.

Ce n’est pas un théorème démontrable au sens classique, mais une thèse : tous les modèles de calcul proposés depuis 1936 (machines à registres, lambda-calcul, fonctions récursives, automates cellulaires…) se sont révélés équivalents à la machine de Turing. Aucun modèle plus puissant n’a jamais été découvert.

Cette équivalence est très profonde : elle suggère que la notion de « calculable » est une propriété intrinsèque, indépendante du formalisme choisi pour l’exprimer.

4.4. Langages Turing-complets

Un langage de programmation est Turing-complet s’il peut simuler une machine de Turing. Concrètement, il suffit qu’il dispose :

• d’une mémoire potentiellement infinie ;
• d’instructions conditionnelles (if) ;
• d’une forme de boucle ou de récursivité.

Tous nos langages courants sont Turing-complets : Python, C, Java, JavaScript, Haskell… et même Scratch ou Brainfuck. (Certains langages très restreints ne le sont pas : par exemple HTML seul, ou les expressions régulières classiques.)

Conséquence : tous les langages Turing-complets peuvent calculer exactement les mêmes fonctions. La calculabilité ne dépend pas du langage utilisé. Ils diffèrent en revanche par leur efficacité, leur lisibilité et leur commodité d’écriture.

5. Classes de complexité : P, NP et NP-complet (hors programme)

L’étude de la calculabilité d’une fonction ne se limite pas à un choix binaire : « calculable » ou « non calculable ». Parmi les fonctions calculables, certaines peuvent l’être rapidement, et d’autres beaucoup moins. On retrouve alors la notion bien connue de complexité algorithmique, qui permet de classer les algorithmes suivant leur dépendance à la taille des données d’entrée.

5.1. La classe P

Sont de « classe P » les problèmes dont l’algorithme de recherche de solution est de complexité polynomiale. On y retrouve tous les problèmes dont la solution est un algorithme de complexité linéaire, quadratique, logarithmique… tout, sauf un algorithme de complexité exponentielle.

Pour le résumer grossièrement, un problème de classe P est un problème que l’on sait résoudre en temps raisonnable (même si grand) :

• le problème du tri d’une liste est dans P (tri fusion en \(\mathcal{O}(n \log n)\)) ;
• le problème de la factorisation d’un grand nombre (sur lequel repose la sécurité du RSA) n’est a priori pas dans P ;
• le problème de la primalité (« ce nombre est-il premier ? ») a longtemps été considéré comme n’étant pas dans P… jusqu’en 2002, où a été découvert le test de primalité AKS , de complexité polynomiale (d’ordre 6). Ce test est donc maintenant dans P.

5.2. La classe NP

Petit détour : déterminisme et non-déterminisme

Une machine de Turing déterministe est telle qu’à chaque étape, l’action à effectuer (symbole à écrire, déplacement, nouvel état) est entièrement déterminée par l’état courant et le symbole lu. À toute exécution correspond donc une suite unique d’instructions. C’est le modèle de tous nos ordinateurs.

Une machine de Turing non-déterministe dispose, à chaque étape, de plusieurs actions possibles parmi lesquelles choisir. On l’imagine de deux manières équivalentes :

• soit elle « devine » toujours le bon choix (vision optimiste) ;
• soit elle explore en parallèle toutes les branches d’un arbre de possibilités (vision divergente).

La machine non-déterministe accepte une entrée s’il existe au moins un chemin d’exécution qui mène à l’acceptation. Elle rejette l’entrée si tous les chemins échouent.

Les machines non-déterministes n’existent pas physiquement : c’est une abstraction théorique commode pour raisonner sur les problèmes.

Définition de NP

Sont de « classe NP » (Non-déterministe Polynomial) les problèmes qu’une machine de Turing non-déterministe peut résoudre en temps polynomial.

Attention : NP ne signifie pas « non polynomial » !

Définition équivalente, plus accessible

Imaginons qu’un oracle nous fournisse une solution candidate. Si on peut la vérifier en temps polynomial, le problème est dans NP. En effet, la machine non-déterministe peut « deviner » la solution dans une de ses branches, et vérifier en temps polynomial qu’elle est correcte.

Sont de classe NP les problèmes dont la vérification d’une solution proposée se fait en temps polynomial.

Un problème de classe NP est donc un problème dont on sait vérifier facilement si une solution proposée marche ou pas :

• la résolution d’un sudoku : si quelqu’un vous montre une grille remplie, vous vérifiez en quelques secondes que les contraintes sont respectées (mais la trouver à partir de zéro est très dur) ;
• la factorisation d’un grand nombre : si on vous propose \(4567 \times 6037\) comme décomposition de \(27,570,979\), vous vérifiez par une simple multiplication ;
• le problème du voyageur de commerce (en version décision : « existe-t-il un trajet de longueur inférieure à \(L\) ? ») : un trajet proposé se vérifie en temps linéaire ;
• le problème du sac à dos 0/1 (en version décision, voir encadré ci-dessous) : un butin proposé se vérifie en temps linéaire ;
• la satisfaisabilité booléenne (SAT) : étant donné une formule booléenne, existe-t-il une affectation des variables qui la rende vraie ? Une affectation candidate se vérifie en temps polynomial.

Sac à dos : un piège classique

Le sac à dos est l’exemple parfait pour saisir la frontière entre P et NP, à condition de bien distinguer ses deux versions.

Sac à dos fractionnaire (les objets sont divisibles : on peut prendre une fraction d’un objet). L’algorithme glouton qui trie les objets par ratio valeur/poids décroissant puis les prend dans l’ordre est optimal. Sa complexité est dominée par le tri : \(\mathcal{O}(n \log n)\). Le problème est dans P.

Sac à dos 0/1 (chaque objet est pris en entier ou pas du tout). L’algorithme glouton tourne toujours en \(\mathcal{O}(n \log n)\)… mais il ne donne plus la solution optimale. Considérons un sac de capacité 10 et trois objets :

L’algorithme glouton commence par prendre A (meilleur ratio). Il reste 4 unités de capacité, insuffisantes pour B ou C qui pèsent 5 chacun. Valeur totale obtenue : 10.

La solution optimale est de prendre B et C (poids total 10, valeur 16). Le glouton est passé à côté : il a un bon ratio, mais il a sacrifié la possibilité d’utiliser tout le sac.

Pour obtenir la solution optimale du sac à dos 0/1, il faut :

• soit la force brute en \(\mathcal{O}(2^n)\) (tester tous les sous-ensembles) ;
• soit la programmation dynamique en \(\mathcal{O}(n \cdot W)\), dite pseudo-polynomiale : polynomiale en la valeur de \(W\), mais comme \(W\) s’écrit avec \(\log_2 W\) bits, c’est en réalité exponentielle en la taille de l’entrée.

Aucun algorithme polynomial et correct n’est connu : le sac à dos 0/1 (en version décision) est NP-complet. C’est précisément cette version qui sert de référence en théorie de la complexité.

À retenir : un algorithme rapide existe (le glouton), mais il est incorrect pour la version 0/1. Un algorithme correct existe (la programmation dynamique), mais il n’est pas vraiment polynomial. C’est cette tension entre rapidité et exactitude qui caractérise les problèmes NP-complets.

Pour les autres problèmes mentionnés plus haut (sudoku, factorisation, voyageur de commerce, SAT), aucun algorithme de résolution meilleur qu’exponentiel n’est connu à ce jour.

5.3. \(P \subset NP\) et les problèmes NP-complets

Tout problème de P se résout en temps polynomial : la même procédure peut servir à vérifier une solution proposée (il suffit de la recalculer et de comparer). On en déduit que \(P \subset NP\) : tout problème de P est aussi dans NP.

Voici une capture d’écran de l’excellente vidéo Nos algorithmes pourraient-ils être BEAUCOUP plus rapides ? (P = NP ?) de David Louapre :

On y retrouve (en vert) la classe P, qui contient les algorithmes de tri ou de recherche dichotomique. En blanc, la classe NP, qui contient en plus les problèmes de factorisation, de sudoku, de sac à dos 0/1, du voyageur de commerce, de SAT…

Problèmes NP-complets

Certains problèmes de NP ont une propriété remarquable : la résolution polynomiale d’un seul d’entre eux ferait basculer tous les problèmes de NP dans P. On dit que ces problèmes sont NP-complets (en rouge ci-dessus).

Concrètement, si vous trouvez un algorithme polynomial pour résoudre le sudoku, vous entraînez avec lui dans P tous les autres problèmes NP, et vous aurez prouvé que \(P = NP\).

Le premier problème prouvé NP-complet est SAT (théorème de Cook-Levin, 1971). Tous les autres problèmes NP-complets connus le sont par réduction à SAT : on montre qu’on peut transformer un problème en SAT (ou inversement) en temps polynomial.

Sont NP-complets, par exemple :

• SAT et ses variantes (3-SAT) ;
• le sac à dos 0/1 (version décision) ;
• le voyageur de commerce (version décision) ;
• la coloration de graphes (à 3 couleurs ou plus) ;
• le sudoku généralisé (sur grille \(n \times n\)).

5.4. La question à un million de dollars

Actuellement, la plupart des chercheurs pensent que \(P \neq NP\), c’est-à-dire que certains problèmes ne pourront jamais avoir une solution polynomiale. Mais personne ne l’a encore prouvé.

Accessoirement, qui tranchera cette question gagnera un million de dollars , promis par la fondation Clay (prix que vous partagerez bien évidemment avec votre professeur de NSI).

Une preuve que \(P = NP\) bouleverserait la cryptographie, l’optimisation et l’intelligence artificielle.