next up previous contents
Next: Mécanique quantique Up: La thèse de Church Previous: La thèse de Church

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

Par ``philosophie de Pythagore", ce que je désignerai par PP0 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 racine : 2. Et l'extraction de la racine est une opération louable du genre de celle qu'on apprend sur les bancs de l'école. On pourrait donc imaginer une nouvelle école pythagoricienne PP1 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 π, 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 π ? Notons qu'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'il existerait une école universelle PPu 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 PPu 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 conceptuellegif 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 PPu sont énumérables. Enumérons-les donc:

f0, f1, f2, f3, f4, f5, f6, f7, ...

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

g(n) = fn(n)+1

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

g(k) = fk(k)

puisque g = fk, et on obtient aussi

g(k) = fk(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 PPu, 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 PPu 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 fk est totale, et alors gk est totale. Dans ce cas g(k) ne peut pas être égale à g(k)+1, g ne peut pas être égale à une fi, et nous avons, effectivement, réfuté l'universalité de PPu. On a démontré l'impossibilité d'énumérer la collection des fonctions totales calculables. La démonstration est constructive : é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'écoles pythagoriciennes de plus en plus larges.
Avec la thèse de Church
Dans ce cas, une école universelle du style PPu 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 fi de PPu ? 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 fi 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 ω1CK-transfinies d'écoles pythagoriciennes, où ω1CK 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. %


next up previous contents
Next: Mécanique quantique Up: La thèse de Church Previous: La thèse de Church

Bruno Marchal
Thu Apr 1 00:14:24 CEST 1999