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 PP

₀ 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'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 PP

₁ 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

π ? 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 PP

_u 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

_u 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'é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 $ω$ ₁^CK-transfinies d'écoles pythagoriciennes, où $ω$ ₁^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. %

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