Résumé : Comment déterminer la manière la plus simple d'obtenir un nombre entier à partir des opérations de base ?

Il existe une mesure de complexité "universelle" qui permet de définir ce qu'on entend par "un object complexe" : un nombre, une image, un texte, un concept mathématique ou autre... La complexité de Kolmogorov. Nous ne l'appliquerons ici qu'au cas des nombres entiers positifs.

En fait, dans la définition classique de l'ensemble des nombres naturels, les mathématiciens utilisent les axiomes dits "de "" en l'honneur de Guiseppe Peano, le mathématicien qui les a le premier explicités (voir Les entiers de Peano et les autres), et parmi ces axiomes, on trouve :

Donc pour construire un nombre ; si suffit d'appliquer plusieurs fois de suite la fonction successeur à . Combien de fois ? fois, bien sûr ! Mais attendez... N'est-ce pas le serpent qui se mord la queue ? Comment peut-on oser définir ... à partir de ? Et voila pourquoi on a inventé aussi l'addition et la multiplication !

Conjointement, ces opérations permettent d'expliquer clairement comment construire un nombre à partir de zéro (ou de un, mais n'ergottons pas).

Par exemple
"" ne peut pas être construit plus simplement qu'en faisant , et de même "", mais au delà, ce n'est plus vrai : , et par exemple , et il n'est en fait pas possible de construire avec des additions et multiplications en en utilisant moins de étapes. On dira que la complexité de est 11.

Ce que l'on note parfois

Preuve de la non calculabilité de K(n) <- cliquer ici

Par exemple, dans une théorie (très !) simplifiée, on pourrait avoir les définitions suivantes de la complexité approchée (avec un petit k) d'un entier n :

Mais rien n'empèche en fait d'utiliser d'autres opérations, comme la soustraction et la division (Comme dans le jeu "le compte est bon" !), mais aussi l'élévation à la puissance, les tours de puissances, les factorielles, les flèches de Knuth et de Conway, la fonction d'Ackermann et même celle de Goodstein, les parties entières des logarithmes et exponentielles dans différentes bases, ou même les parties entières d'autres fonctions réelles comme les cosinus et sinus hyperboliques, etc... Nous verrons plus loin que ce n'est pourtant pas si évident.

L'idée est bien sûr d'approcher le plus possible la complexité de Kolmogorov, qui n'est pas calculable.

Le petit programme ci-dessous permet alors de calculer la complexité d'un nombre en utilisant uniquement les opérations +, et x , avec l'algorithme légèrement différent suivant :

On obtient

Est-ce que les complexités résultent toutes d'un produit ou d'un produit +1 ? FAUX :

Obtenu avec Plotly

On démontre que le plus grand nombre de complexité est :
Par exemple pour , et le plus grand entier de complexité 10 est
Pour , et le plus grand entier de complexité 12 est

Donc

En pratique c'est pratiquement toujours beaucoup moins que cette borne supérieure

On remarque que les décompositions de obtenues, même les sont toutes de la forme avec a =2,3,5,7 et r = 0,1,2,3,4,5,6
Donc le programme suivant ne recherche que ces formes.

L'idée qui est derrière la définition de la complexité en termes uniquement d'additions et de multiplications, c'est que, bien qu'il soit toujours possible d'addtionner fois le chiffre "1", pour construire un nombre on voudrait savoir, s'i c'est possible d'une manière qui soit plus efficace, et si possible la plus efficace possible.

Certes, si nous faisions intervenir la soustraction dans notre calcul de complexité, nous pourrions parvenir à construire un nombre en moins d'opérations que ; par exemple , mais si on admet la soustraction, il se trouve que et comme , on pourrait "ramener" à 10.

Mais attendez, Est ce que cela à un sens de construire un nombre à partir d'un nombre plus grand ? est-ce que ce n'est pas le serpent qui se mord la queue, et la porte ouverte à des "boucles" de nombres qui se construiraient l'un l'autre mais ne pourraient être construits (d'une manière efficace) par des nombres plus petits ?

Nos constructions "minimales" avec opérations sont un réalité une description du nombre d'étapes qu'il faut pour construire un nombre uniquement à partir de "1" et en ne faisant intervenir que des nombres plus petits que .

donc :

Eh bien oui, de même qu'on peut définir la multiplication comme une suite d'additions, à partir de la multiplication on peut définir l'exponentiation à partir de la multiplication ; après tout, c'est , fois

SI nous ajoutons donc la fonction puissance, quel est le plus grand nombre de complexité donné ?

Pour nous notons que , et si nous cherchons le maximum de avec , est toujours plus grand que , par contre devient encore plus grand dès que , et dès que =, dès que , dès que

En fait . En différenciant par rapport à on trouve

#TBC

Mais attention : ce que nous cherchons ici le maximum de ce que l'on peut obtenir au moyen de l'addition, de la multiplication et de l'exponentiation (plus les parenthèses) de chiffres "1". Donc ce qui vaut , ce n'est pas mais

Et pour par exemple , il est clair que

#TBC ? exponentiation ? knuth ? Ackermann ? tau (inverse de sigma, la fonction de Rado)? Graham ? Tree ?

#TBC

Existe-il un nombre dont la complexité serait supérieure à ? Si c'est le cas, on peut douter de la validité de la construction de Peano des entiers !

Ceci suggère de chercher à caractériser les entiers de complexité maximale.

Mes recherches mathématiques
beaver
demonstr-ncalc
commentaires
autorep