Tous le monde à entendu parler du paradoxe de Russel, la question qui rend la théorie des ensembles incohérente : « L'ensemble des ensembles qui ne se contiennent pas se contient-t-il ? ». La contradiction se trouve dans la définition de cet ensemble. Ce paradoxe apparait lorsqu'on s'autorise à écrire des propositions logiques du second ordre.
Mais il existe un autre paradoxe d'une autre nature que celui de Russel, et qui a l'avantage d'être entièrement constructif. C'est le paradoxe de Godel-Turing qui dévoile le monde du calcul et le monde du raisonnement qui sont deux mondes qui coïncident exactement.
Un programme `m` appliqué à une donnée `x` lance un calcul noté `m(x)`. Et ce calcul peut produire au bout d'un temps fini un résultat `y` ce qui se note `m(x)"="y`, ou bien ne jamais s'arrêter et donc ne jamais donner de résultat ce qui se note `m(x)"="∞`, l'infini de Turing. Et on notera `m(x)"≠"oo` pour signifier que le calcul `m(x)` s'arrète et produit donc un résultat.
Remarquez que le programme `m` est aussi une donnée. La question posée est alors la suivante :
Existe-t-il un programme `p` qui prend en entrée n'importe quel programme `m` et n'importe quelle donnée `x`, et qui détermine en un temps fini si le calcul `m(x)` s'arrête ou non ?
La réponse à cette question est non. Et c'est Alan Turing qui le démontre par l'absurde en supposant l'existence d'un tel programme `p`. Il utilise pour la démonstration le procédé de la diagonal de Cantor.
Supposons la décidabilité du problème de l'arrêt, c'est à dire qu'il existe un programme `p` qui prend en entrée n'importe quel programme `m` et n'importe quelle donnée `x`, et qui détermine en un temp fini si le calcul `m(x)` s'arrête ou non ?. Nous allons montrer que cela entraine une contradiction. Le programme `p` vérifie :
`p(m,x)"="0 <=> m(x)"="oo`
`p(m,x)"="1<=> m(x)"≠"oo`
On programme une variante `q`, qui prend en entrée un programme `m` quelconque et une donnée `x`, et qui s'arrête si `m(x)` ne s'arrête pas, et qui ne s'arrête pas si `m(x)` s'arrète ?. Le programme `q` peut s'écrire par exemple comme suit :
`q={m,x "|" s"="p(m,x);(((s"="1) => "return" oo),((s"="0) => "return" 0))}`
On reprend la notation en ruby du bloc de code entre crochet `{...}` avec les arguments d'entrée énumérés avant le symbole pipe `|`, puis les instructions séparées par des point-virgules, puis avec une instruction « case ... of » sous forme de vecteur, et où `"return" oo` signifie lancer une boucle sans fin, et `"return" 0` signifie arrêter le programme en retournant `0`. Nous avons, pour tout programme `m` et toute donnée `x` :
`q(m,x)"≠"oo<=> m(x)"="oo`
`q(m,x)"="oo<=> m(x)"≠"oo`
On considère un programme `Ω` qui énumère tous les programmes. Le fait que l'ensemble des programmes soit énumérable découle des considérations générales sur le langage et le calcul qui sont à la base de la logique et qui sont décrites ici : Logique.
On représente un énumérateur par un programme `Ω` qui appliqué à un entier `n` va produire la `n`-ième donnée énumérée par `Ω`. Puis on complète ce programme `Ω` pour que, appliqué à une donnée autre qu'un entier, il retourne une donnée que l'on fixe arbitrairement en l'élément `"Out"`. Cette dernière spécification est ajoutée pour faire de `Ω` un programme complètement défini.
On note l'ensemble des données énumérées par le programme `Ω`, par le même symbole `Ω` en tant qu'ensemble :
`Ω={Ω(1),Ω(2),Ω(3),Ω(4),...}`
`bbbW` est l'ensemble de toutes les données possibles. Il est important de bien comprendre la distinction entre un programme appartenant à Ω et la fonction mathématique que le programme calcule et qui appartient à `bbbW"→"bbbW"∪"{∞}`. La fonction ne s'intéresse qu'au résultat ou au calcul sans fin, alors que le programme décrit le processus qui atteint ce résultat ou qui se lance dans un calcul sans fin. Deux programmes `A, B` distincts peuvent calculer une même fonction. Dans ce cas, on dira qu'ils sont équivalents, et on écrira `A"≈"B`. Nous avons :
`A"≈"B <=> AAx "∈" bbbW, A(x)"="B(x)`
Notez que l'égalité `A(x)"="B(x)` s'applique parmi les éléments de `bbbW"∪"{oo}`. C'est à dire que si `A(x)"="oo` alors `B(x)"="oo`, et réciproquement. Autrement dit, si le calcul `A(x)` ne s'arrète pas alors le calcul `B(x)` ne doit pas s'arrêter, et réciproquement. Nous avons évidemment :
`A"="B => A"≈"B`
Reprenons la suite de notre démonstration. L'étape suivante consiste à construire un programme `C` par le procédé de la diagonale de Cantor, tel que pour tout entier `n`, nous ayons :
`C(n) = q(Ω(n),n)`
Puis on complète ce programme `C` pour que, appliqué à une donnée autre qu'un entier, il retourne une donnée que l'on fixe arbitrairement en l'élément `"Out"`. Cette dernière spécification est ajoutée pour faire de `C` un programme complètement défini, appartenant donc à `Ω`. Le programme `C` peut s'écrire comme suit :
`C = {n | (( n "∈" NN => "return" q(Ω(n),n) ) ,(n "∉" NN => "return Out"))}`
Littéralement, `Ω` codifit tout les programmes en les identifiant à un entier. Le programme `C` appliqué à l'entier `n` s'arrête si le programme numéro `n` appliqué à l'entier `n` ne s'arrête pas, et il ne s'arrête pas si le programme numéro `n` appliqué à l'entier `n` s'arrête. Le programme `q` qui prend en entrée un programme `m` et une donnée `x`, s'arrête si `m(x)` ne s'arrête pas, et ne s'arrête pas si `m(x)` s'arrète.
Le programme `C` prend en entrée une donnée et retourne comme résultat une donnée. Donc il appartient à `Ω`. Donc il est énuméré par `Ω`. Donc il existe un entier `k` tel que `C"="Ω(k)`. Ainsi `C` est le programme numéro `k`. L'entier `k` est calculable. Il suffit de les passer en revue en les testant un par un jusqu'à tomber sur le bon `k` vérifiant l'égalité `C"="Ω(k)`. Soit un tel entier `k`. Nous avons :
`C"="Ω(k)`
Et par définition nous avons :
`AA n "∈" NN, q(Ω(n),n)"="C(n)`
On constate alors l'existence d'une contradiction.
`C(k)"≠"∞ => q(C,k)"="oo`
`q(Ω(k),k)"="oo => C(k)"="∞`
Et
`C(k)"="∞ => q(C,k)"≠"oo`
`q(Ω(k),k)"≠"oo => C(k)"≠"∞`
Raisonner c'est calculer, faire une démonstration c'est faire un calcul. Etant donné un langage logique et un système de démonstration. Il existe un programme qui énumère toutes les propositions démontrables c'est-à-dire toutes les tautologies. Cela découle des considérations générales sur le langage et le calcul qui sont décrites ici : Logique.
Le complément c'est-à-dire l'ensemble des propositions qui ne sont pas des tautologies c'est-à-dire qui sont indémontrables, peut soit être énumérable ce qui signifit qu'il existe un programme qui les énumère, ou soit être non-énumérable ce qui signifit qu'il n'existe pas de programme qui les énumères. Dans les cas triviaux, tout est énumérables. Dans les cas non trivaux l'ensemble des propositions indémontrables n'est pas énumérable.
Si l'ensemble des propositions indémontrables n'est pas énumérable, alors tout n'est pas calculable.
se traduit en terme logique par l'inexistence de démonstration pour trancher certain énnoncé. Et donc cela traduit l'inhérente incomplétude des théories finies dès qu'elles sont suffisament complexes pour pouvoir implémenter une machine de Turing, c'est à dire en terme logique, dès qu'elles contiennent l'arithmétique.
---- 3 mars 2023 ----