Décidabilité et calculabilité

I. Introduction⚓︎

Programme en tant que donnée

Un compilateur, un débugueur, un interpréteur sont des programmes qui prennent en paramètres d’autres programmes. C’est aussi le cas d’un logiciel de téléchargement, ou d’un système d’exploitation qui va faire tourner d’autres programmes. Ainsi, tout programme peut être perçu comme une donnée pour un autre programme.

Calculabilité et décidabilité, deux notions proches

Étudier la calculabilité d’une fonction ou la décidabilité d’un problème, c’est chercher si cette fonction peut être calculée, ou si ce problème peut être résolu, à l’aide d'un algorithme.

II. Problèmes de décision et décidabilité⚓︎

Définitions Un problème de décision est un problème qui prend une entrée (une donnée) et renvoie en sortie oui ou non. Un problème de décision est dit décidable s'il existe un algorithme qui, pour chaque entrée, répond par oui ou par non à la question posée par le problème. S'il n'existe pas un tel algorithme, le problème est dit indécidable.

2.1. Classement des problèmes de décision⚓︎

2.1.1. Problèmes ayant une solution en temps polynomial⚓︎

Deux entiers n et p sont-ils premiers entre eux ?
Un programme en Python est-il syntaxiquement correct ?
Un graphe est-il connexe ?

On note P l’ensemble des problèmes de décision résolubles en temps polynomial.

2.1.2. Problèmes ayant une solution, mais pas en temps polynomial⚓︎

Une grille de Sudoku a-t-elle une solution ?
Un graphe donné peut-il être coloré avec trois couleurs sans que deux sommets voisins aient la même couleur ?
Étant donné un entier d, des villes et les distances entre les villes, existe-t-il un trajet passant par toutes les villes de longueur inférieur à d ? (problème du voyageur de commerce, TSP).

Problèmes NP

Entre les catégories 1 et 2, on peut considérer la catégorie des problèmes NP (Non déterministe Polynomial). Il s’agit des problèmes pour lesquels la vérification d’une solution candidate donnée est en temps polynomial, mais la recherche d’une solution est a priori en temps exponentiel. On se demande s’il existe pour ces problèmes des solutions en temps polynomial. C’est une des plus grandes questions ouvertes en informatique. Est-ce que P = NP ?

2.2. Problèmes pour lesquels on ne connaît pas d’algorithmes⚓︎

Étant donné des entiers n et k et un chiffre c, existe-t-il une expression avec les opérateurs +, -, ×, /, √ et ! utilisant au plus k fois le chiffre c dont la valeur est n ? (problème Tchisla)

2.3. Problèmes indécidables (pour lesquels on sait qu’il n’existe pas d’algorithme)⚓︎

Peut-on paver le plan avec des polyominos de formes données ?

Un polyomino est une pièce type Tetris, c’est-à-dire constituée de carrés identiques juxtaposés. Si certains polyominos permettent de former un rectangle, on pourra paver le plan, mais avec les pièces données ci-dessous, cela semble difficile.

En 1970, Solomon W. Golomb montre que ce problème est indécidable, qu’il n’existe pas d’algorithme acceptant un nombre fini de formes de polyominos en entrée et indiquant en sortie si on peut paver le plan avec ces formes.
Une équation diophantienne donnée possède-t-elle une solution entière ?

Une équation diophantienne est une équation polynomiale à plusieurs variables à coefficient entiers, comme \(2x – 4 y + 6z = 0\), \(x^2 – 4xy + y^3 = 8\) ou \(x^3 + y^3 + z^3 = 42\), etc.

En 1900, David Hilbert demande s’il existe un algorithme capable de décider pour n’importe quelle équation diophantienne si elle possède ou non une solution. C’est le dixième problème d’une série de 23 problèmes difficiles qu’il pose au congrès international des mathématiciens à Paris.

Ce n’est qu’en 1970 qu’un mathématicien russe, Iouri Matiassevitch, prouve qu’il n’existe pas un tel algorithme, donc qu’il s’agit d’un problème indécidable. Cela ne signifie pas qu’une équation donnée ne peut pas être résolue, mais qu’il n’existe pas une méthode unique applicable à toutes les équations diophantiennes.

A propos des équations diophantiennes : problème de la somme de trois cubes
• \(x^3 + y^3 + z^3 = 43\) admet pour solution \(x = 2\), \(y = 2\) et \(z = 3\).
• \(x^3 + y^3 + z^3 = 42\) est restée sans solution jusqu’en septembre 2019 !

Andrew Booker et Andrew Sutherland l’ont trouvé après une recherche exhaustive sur Charity Engine.

Des travaux mathématiques préalables leur ont permis de réduire les cas à explorer plutôt que de faire une simple triple boucle.

Plus d’un million d’heures de calcul parallélisé (114 ans) ont permis de trouver comme solution :

\(x = -80538738812075974\)

\(y = 80435758145817515\)

\(z = 12602123297335631\).

En mars 2019, Andrew Booker avait trouvé une solution à \(x^3 + y^3 + z^3 = 33\).

On connaît maintenant des solutions à \(x^3 + y^3 + z^3 = k\) pour tous les entiers \(k\) entre \(0\) et \(1000\) à l’exception des valeurs \(114\), \(390\), \(627\), \(633\), \(732\), \(921\) et \(975\) (en février 2024).

Programme en tant que donnée, calculabilité, décidabilité, et problème de l'arrêt⚓︎

Comprendre que tout programme est aussi une donnée.
Comprendre que la calculabilité ne dépend pas du langage de programmation utilisé.
Montrer, sans formalisme théorique, que le problème de l’arrêt est indécidable.
Thèse de Church

Décidabilité - Calculabilité - Cédric Gerland (18:22)

Indécidabilité du problème de l’arrêt⚓︎

On considère une fonction, qui pour tout algorithme et valeur d’entrée pour cet algorithme, indique si l’algorithme s’arrête ou pas. Cette fonction est incalculable, ce qui revient à dire que le problème de l'arrêt est indécidable. Ce résultat a été prouvé par Alan Turing en 1936.

En d’autres termes, il n'existe pas de programme qui prenne en argument n'importe quel programme avec une valeur d’entrée et qui, en temps fini, renvoie « oui » si l'exécution du programme reçu en argument finit par s'arrêter avec l’entrée spécifiée et « non » s'il ne finit pas.

Proof That Computers Can't Do Everything (The Halting Problem) (07:52)

Démonstration :

Preuve n°1 (classique)

On suppose qu’il existe un programme halt, qui prend en argument le code d’un programme P (sous forme de chaîne de caractères) et un argument x de P et renvoie True si P s’arrête sur x, et False sinon.

On s’intéresse plus précisément aux programmes qui prennent en paramètre une chaine de caractères : x est donc une chaîne de caractères. On considère la fonction suivante :
🐍 Editeur
```
def contradiction(P: str):
    if halt(P, P):
        while True:
            print("Le code boucle")
    else:
        print("Le code s’arrête")
```
Que se passe-t-il quand on lance contradiction(code_contradiction) ?
- Soit cet appel s’arrête : dans ce cas, halt(code_contradiction, code_contradiction) renvoie True et on entre dans une boucle infinie. C’est absurde !
- Soit cet appel ne s’arrête pas : halt(code_contradiction, code_contradiction) renvoie False, puis le programme s’arrête !
Dans les deux cas, on aboutit à une contradiction. On en déduit que le programme halt ne peut pas exister.

Preuve n°2

On suppose qu’il existe une fonction halt(f, x) -> bool: qui prend en paramètres le code source d’une fonction f et un argument x de cette fonction puis indique si f(x) s’arrête ou boucle indéfiniment.

On considère la fonction contradiction, prenant en argument un entier x.
🐍 Editeur
```
def contradiction(x):
    if halt(code_contradiction, x):
        while True:
            print("Le code boucle")
    else:
        print("Le code s’arrête")
```
Que fait contradiction(0) (ou contradiction(37), etc.) ?
- Si halt(code_contradiction, 0) == True, alors contradiction(0) doit s’arrêter. Or, dans ce cas, on entre dans une boucle infinie !
- A l’inverse, si halt(code_contradiction, 0) == False, alors contradiction(0) ne s’arrête pas, et pourtant, dans ce cas, selon le code, contradiction(0) s’arrête !
Dans les deux cas, on arrive à une contradiction, ce qui prouve que la fonction halt n’existe donc pas !!!

Le PROBLEME DE L'ARRET est donc INDECIDABLE !