La thèse de Church permet de réhabiliter une ``philosophie de Pythagore"

Par ``philosophie de Pythagore", ce que je désignerai par PP$$<sub>0</sub> ou simplement PP, j'entends l'idée selon laquelle tout est nombre (naturel) ou rapport de nombres (naturels). Après avoir découvert les rapports harmoniques, Pythagore aurait, en effet, postulé que, en particulier, toutes les grandeurs mesurables devraient pouvoir s'écrire sous forme de quotient de nombres naturels. Cette philosophie a été jugée réfutée après la découverte, par les Pythagoriciens eux-mêmes, que la longueur d'un coté d'un carré de surface 2 ne peut pas s'écrire sous forme d'un tel rapport. Il n'empêche que cette longueur, de la diagonale de ce carré de surface 2, peut s'écrire, et s'écrit traditionnellement sous forme de raci$ne\; :$ 2$.\; Et\; l\text{'}extraction\; de\; la\; racine\; est\; une\; opération\; louable\; du\; genre\; de\; celle\; qu\text{'}on\; apprend\; sur\; les\; bancs\; de\; l\text{'}école.\; On\; pourrait\; donc\; imaginer\; une\; nouvelle\; école\; pythagoricienne\; PP$ $$<sub>1</sub> selon laquelle tout est nombre ou rapport de nombres ou racine de nombre. Les mathématiciens savent cependant qu'une telle philosophie aurait été jugée réfutée au 19ième siècle lorsqu'Abel, en 1824, démontre que d'une façon générale les solutions d'une équation polynomiale de degré supérieur à 4 ne peuvent pas s'écrire sous forme de radicaux. De même il est bien connu qu'Hermite, en 1873, et Lindemann, en 1882 (voir Simmons 1992) démontreront que le nombre d'Euler $e$ et le nombre $\pi$, dont les décimales sont pourtant calculables, ne peuvent pas être solution d'une équation polynomiale, et donc en particulier, n'admettent pas de descriptions sous forme radicales (en terme de racine, somme, soustraction et rapport). Mais pourquoi ne pas imaginer à nouveau une école pythagoricienne selon laquelle tout est nombre ou combinaisons de nombre, où les combinaisons comprennent les rapports, les racines, et le minimum indispensable pour calculer les solutions des équations polynomiales, ainsi que $e$ et $$ \pi $?Notons\; qu\text{'}un\; nombre\; réel\; (positif)\; peut\; être\; codé\; par\; une\; fonction\; des\; naturels\; dans\; les\; naturels.\; Par\; exemple,\; ayant\; choisi\; une\; base,\; en\; envoyant\; 0\; sur\; la\; partie\; entière,\; 1\; sur\; la\; première\; décimale,\; 2\; sur\; la\; 2ème,\; ainsi\; de\; suite.\; La\; question,\; alors,\; est\; de\; savoir,\; si\; la\; suite\; des\; écoles\; pythagoriciennes\; va\; converger,\; dans\; le\; sens\; qu\text{'}il\; existerait\; une\; école\; universelle\; PP$ $$<sub>u</sub> capable de calculer toutes les fonctions calculables. Il existerait alors une collection finie d'opérations calculables, dont les combinaisons finies et descriptibles (communicables) permettraient de calculer toutes les fonctions calculables, et en particulier tous les réels calculables. Si on avait demandé s'il existe une école capable de calculer tous les réels, la réponse aurait été non. On connait l'argument par la diagonale de Cantor montrant que les réels sont indénombrables, alors que les fonctions de l'école PP$$<sub>u</sub> sont clairement dénombrables puisqu'on peut énumérer les descriptions des combinaisons finiment communicables, combinaisons des opérations calculables admises comme primitive par cette école. Curieusement l'argument de la diagonale semble pouvoir réfuter, non seulement l'existence d'une école capable de calculer tous les réels, mais semble pouvoir réfuter aussi l'existence d'une école capable de calculer toutes les fonctions calculables, ou tous les réels calculables. C'est avec l'argument de la diagonale que Kleene a en effet estimé, pendant un temps, pouvoir réfuter la ``définition" de Church. L'échec de cette réfutation, autrement dit la fermeture de l'ensemble des fonctions calculables pour l'opération de diagonalisation, constitue la motivation conceptuelle la plus profonde pour la thèse de Church. C'est en découvrant cette fermeture que Kleene est devenu un partisan zélé de la thèse de Church. Cela vaut la peine de regarder pourquoi la diagonalisation semble pouvoir réfuter la thèse de Church. On retrouvera par ailleurs le fait que la thèse entraîne l'incomplétude. En effet, j'ai déjà mentionné le fait que les fonctions calculables par l'école PP$$_u sont énumérables. Enumérons-les donc:

$f$₀, f₁, f₂, f₃, f₄, f₅, f₆, f₇, ...

mais alors la fonction $g$ définie au moyen de la première diagonalisation

$g(n)\; =\; f$_n(n)+1

n'est pas calculable par l'école PP$$_u. En effet, si elle était calculable par l'école PP$$_u, elle appartiendrait à l'énumération. Il existerait alors un nombre $k$ tel que $g\; =\; f$_k. On pourrait procéder alors à une deuxième diagonalisation, en appliquant $g$ sur l'indice $k$ correspondant à sa description. On obtient

$g(k)\; =\; f$_k(k)

puisque $g\; =\; f$_k, et on obtient aussi

$g(k)\; =\; f$_k(k) + 1

par définition de k, et donc on a montré:

$g(k)\; =\; g(k)\; +\; 1$

Absurde ? Aurions-nous réfuté l'universalité de PP$$_u, aurions-nous réfuté la thèse de $Church\; ?En\; réalité,\; ce\; couple\; de\; diagonalisations\; ne\; réfute\; pas\; la\; thèse\; de\; Church,\; mais\; entraîne,\; avec\; et\; sans\; la\; thèse\; de\; Church,\; de\; nombreuses\; conséquences\; intéressantes.$

Sans la thèse de Church

Si les pythagoriciens de l'école PP$$_u prétendent que leurs procédures ne définit que des fonctions au sens habituel du terme, c'est-à-dire des fonctions totales, c'est-à-dire des fonctions définies sur chaque nombre naturel, alors chaque $f$_k est totale, et alors $g$_k est totale. Dans ce cas $g(k)$ ne peut pas être égale à $g(k)+1$, $g$ ne peut pas être égale à une $f$_i, et nous avons, effectivement, réfuté l'universalité de PP$$_u. On a démontré l'impossibilité d'énumérer la collection des fonctions totales calculables. La démonstration est constructi$ve\; :étant\; donné\; une\; énumération\; de\; fonctions\; totales\; calculables,\; la\; diagonalisation\; permet\; de\; générer\; une\; nouvelle\; fonction\; totale\; calculable.\; La\; diagonalisation\; fait\; ici\; office\; de\; limite\; constructive\; permettant\; de\; générer\; une\; hiérarchie\; transfinie\; d\text{'}écoles\; pythagoriciennes\; de\; plus\; en\; plus\; larges.$

Avec la thèse de Church

Dans ce cas, une école universelle du style PP$$_u existe, et il en existe même beaucoup (FORTRAN, LISP, le jeu de la vie de Conway [Wainwright, 1974], le problème de $n$ corps [Moore, 1990], l'ordinateur de von Neumann, l'ordinateur quantique de Deutsch [Deutsch, 1985], etc.). Que se passe-t-il alors avec l'énumération des fonctions $f$_i de $PP$ $$_u ? Comme on a démontré que $g(k)\; =\; g(k)\; +\; 1$, on a démontré que $g$ n'est pas définie en $k$. La machine universelle qui calcule $g$ sur $k$ ne s'arrête pas. On a démontré que toute énumération de fonctions qui contient toutes les fonctions totales calculables contient nécessairement des fonctions partielles calculables, c'est-à-dire non partout définies. Nous sommes aussi arrivés à deux pas d'un phénomène d'incomplétude. En effet, aucune machine universelle, ni aucune théorie complète et axiomatisable ne peut nous permettre de distinguer uniformément les indices des fonctions totales calculables des indices des fonctions partielles calculables, puisque cela permettrait en parcourant les $f$_i d'extraire une sous-énumération complète des fonctions totales calculables. Mais alors la double diagonalisation s'ébranlerait à nouveau. Notons qu'avec la thèse de Church, il est possible de préciser les conséquences, sans la thèse de Church, de cette double diagonalisation, en construisant, par exemple, des hiérarchies $\omega$₁^CK-transfinies d'écoles pythagoriciennes, où $\omega$₁^CK représente l'ordinal de Church et Kleene. Il est le plus petit ordinal non constructif, voir [Church and Kleene, 1937].

Avec la thèse de Church, la vieille philosophie de Pythagore est réhabilitable sous la forme ``tout est nombre ou transformation universelle de nombre". Par transformation universelle d'un nombre, j'entends simplement le travail d'une machine universelle appliquée à ce nombre. Le prix de la ``réhabilitation" est qu'on ne peut pas prédire, d'une façon générale, le produit d'une transformation universelle, ni même s'il y en a un. On doit alors reconnaître le caractère universel et objectif (machine-indépendant), de l'incomplétude. %