🔢 mathematics

Inexpressibility in Exp-Minus-Log

Ce papier établit que le système Exp-Minus-Log, qui réduit les fonctions élémentaires à une constante et une seule opération binaire, ne peut exprimer que des nombres calculables, prouvant ainsi que $\Omega_U$ de Chaitin est inexprimable dans ce cadre.

Auteurs originaux : Mark Carney

Publié 2026-05-05

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Mark Carney

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous possédez une cuisine magique et toute-puissante. Dans cette cuisine, vous ne disposez pas d'un ensemble complet d'outils comme des mixeurs, des fours ou des batteurs. À la place, vous n'avez qu'un seul outil spécial, appelons-le la « Baguette Magique » (représentée dans l'article par E), et un seul ingrédient : le nombre 1.

L'article de Mark Carney explore ce qui se passe si vous essayez de cuisiner chaque nombre possible en utilisant uniquement cette baguette et cet ingrédient.

La Recette de la Baguette Magique

La baguette fonctionne d'une manière très spécifique. Si vous la pointez vers deux choses, disons A et B, elle effectue un tour de passe-passe précis : elle prend l'exponentielle de A (une façon élégante de la faire croître très rapidement) et soustrait le logarithme de B (une façon de la réduire).

La Formule : Résultat = exp(A) - log(B)

Les chercheurs originaux (Odrzywo lek) ont montré qu'avec seulement ce tour de passe-passe et le nombre 1, vous pouvez en fait recréer presque tout ce que nous considérons habituellement comme des « mathématiques standards ». Vous pouvez construire des nombres entiers, des fractions, le nombre $\pi$ , $e$ , et même des fonctions complexes comme le sinus et le cosinus. C'est comme être capable de préparer un gâteau de mariage entier en utilisant uniquement une seule cuillère et une tasse de farine.

La Grande Question : Pouvez-vous Cuisiner Tout ?

L'article pose une question plus profonde : Y a-t-il quelque chose que cette cuisine ne peut pas préparer ?

Pour répondre à cela, l'auteur compare cette cuisine à la « Baguette Magique » à un ensemble connu de nombres appelés les nombres EL (du nom du mathématicien Timothy Chow). L'article démontre que la cuisine à la Baguette Magique et la cuisine de Chow sont en fait le même endroit. Elles peuvent produire exactement la même liste de nombres.

L'Ingrédient « Incuisinable » : $\Omega$ de Chaitin

L'auteur introduit ensuite un ingrédient très étrange et théorique appelé $\Omega$ de Chaitin (Oméga).

Qu'est-ce que c'est ? Imaginez un nombre qui représente la probabilité qu'un programme informatique s'arrête (halting) ou tourne indéfiniment.
Pourquoi est-il spécial ? Ce nombre est « non calculable ». Ce n'est pas simplement un nombre que nous n'avons pas encore calculé ; il est mathématiquement impossible pour tout ordinateur (peu importe sa puissance) d'écrire jamais ses chiffres exacts ou de prédire son chiffre suivant. C'est un nombre qui existe, mais il est fondamentalement « inaccessible » par n'importe quelle recette étape par étape.

La Découverte Principale

L'article prouve une règle simple mais puissante : Chaque nombre que vous pouvez créer avec la Baguette Magique est « calculable ».

Voici la logique en anglais simple :

Les Ingrédients sont Sûrs : Vous commencez avec le nombre 1 (qui est facile à calculer).
Le Processus est Sûr : La Baguette Magique ne fait que deux choses : exp et log. L'article montre que si vous donnez à ces outils un nombre qu'un ordinateur peut calculer, ils produiront un résultat qu'un ordinateur peut aussi calculer.
La Conclusion : Puisque vous commencez avec un nombre calculable et n'utilisez que des outils calculables, chaque nombre unique que vous pouvez construire dans ce système doit être calculable.

Comme $\Omega$ de Chaitin n'est pas calculable, il est impossible de le construire dans cette cuisine.

Le Verdict Final

L'article conclut par un « Théorème Formel d'Inexpressibilité ». En termes simples :

La Cuisine à la Baguette Magique peut produire une liste immense et infinie de nombres (incluant $\pi$ , $e$ , et tous les nombres utilisés en ingénierie et en physique).
Cependant, il existe un vaste océan de nombres que la cuisine ne pourra jamais toucher.
$\Omega$ de Chaitin est le « porte-drapeau » de ces nombres inaccessibles. C'est une preuve concrète qu'il existe des vérités mathématiques qui ne peuvent pas être exprimées en utilisant ce système spécifique de règles.

Une Analogie Simple

Imaginez le système de la Baguette Magique comme un ensemble de Lego qui ne contient que des briques rouges.

Vous pouvez construire une maison, une voiture, un château ou une fusée (ce sont les nombres « calculables » comme $\pi$ et $e$ ).
Mais si quelqu'un vous demande de construire une brique bleue, vous ne pouvez pas. Peu importe combien de briques rouges vous empilez, vous ne créerez jamais une brique bleue.
$\Omega$ de Chaitin est cette « brique bleue ». Elle existe dans l'univers des mathématiques, mais elle est faite d'un matériau (la non-calculabilité) qui ne peut tout simplement pas être construit en utilisant les briques rouges (le système EML) dont vous disposez.

En résumé : L'article confirme que bien que ce système à fonction unique soit incroyablement puissant et couvre presque tous les nombres que nous utilisons dans la vie quotidienne et la science, il possède une limite stricte. Il ne peut pas atteindre les nombres « non calculables », prouvant que certains concepts mathématiques sont à jamais hors de portée de cette façon spécifique de les écrire.

Résumé technique : Inexpressibilité dans Exp-Minus-Log

Énoncé du problème
L'article comble une lacune dans la compréhension théorique du système Exp-Minus-Log (EML), défini à l'origine par Odrzywo lek [4]. Ce système réduit toutes les fonctions élémentaires, constantes et opérations sur les nombres complexes à un seul opérateur binaire, $E(\alpha, \beta) = \exp(\alpha) - \log(\beta)$ , et à la constante « 1 ». Bien que le travail d'Odrzywo lek ait été largement constructif et existentiel — démontrant comment exprimer les fonctions élémentaires standards —, il n'a pas établi de théorème formel d'inexpressibilité. Plus précisément, il restait une question ouverte de savoir si le système EML pouvait exprimer des nombres réels non calculables. Cet article vise à caractériser les limites de l'expressibilité EML en déterminant le statut de calculabilité de tous les nombres représentables au sein du système.

Méthodologie
Les auteurs utilisent une combinaison de logique formelle, d'analyse calculable et de théorie de l'information algorithmique pour établir les frontières du système EML. La méthodologie se déroule en trois étapes logiques :

Équivalence formelle : L'article établit d'abord une équivalence rigoureuse entre les nombres EML d'Odrzywo lek et les nombres EL de Chow [2]. En fournissant des substitutions syntaxiques explicites, les auteurs démontrent que le corps des nombres EML est identique au corps des nombres EL (le plus petit sous-corps de $\mathbb{C}$ fermé sous $\exp$ et $\log$ ).
Analyse de la calculabilité : S'appuyant sur des résultats de l'analyse calculable (spécifiquement [7] et [6]), les auteurs analysent la calculabilité des opérations impliquées. Ils exploitent le fait que la fonction exponentielle est calculable sur toutes les entrées complexes calculables. Pour le logarithme, ils traitent les problèmes de coupure de branche en prouvant que, pour toute expression EML définie, l'argument du logarithme soit se situe sur l'axe réel négatif (où la valeur est calculable via le module et $\pi$ ), soit est séparé de la coupure de branche par une distance rationnelle.
Preuve inductive de calculabilité : En utilisant l'induction structurelle sur la syntaxe des expressions EML, les auteurs prouvent que toute expression EML définie évalue à un nombre complexe calculable.
Sélection de témoin : Pour démontrer l'inexpressibilité, l'article utilise $\Omega_U$ de Chaitin (la probabilité d'arrêt d'une machine de Turing universelle préfixée) comme témoin canonique. $\Omega_U$ est connu pour être énumérable à gauche mais non calculable.

Contributions et résultats clés
L'article produit les résultats principaux suivants :

Théorème d'équivalence : L'ensemble des nombres expressibles en EML est prouvé être exactement l'ensemble des nombres EL de Chow ($EML = EL$).
Théorème de calculabilité : L'article prouve que tout nombre expressible en EML est calculable. Plus précisément, pour toute expression EML fermée $\phi$ dont la valeur est définie, $[[\phi]]$ est un nombre complexe calculable. Par conséquent, l'ensemble des réels constructibles en EML ( $EML_{\mathbb{R}}$ ) est un sous-ensemble des réels calculables ( $\text{Comp}_{\mathbb{R}}$ ).
Théorème d'inexpressibilité : En combinant la calculabilité des nombres EML avec la non-calculabilité de $\Omega_U$ de Chaitin, l'article prouve formellement que $\Omega_U \notin EML_{\mathbb{R}}$ .
Implication de la théorie de la mesure : Puisque l'ensemble des nombres EML est dénombrable (en raison de la dénombrabilité de la syntaxe), l'ensemble des réels non expressibles en EML a une mesure de Lebesgue pleine sur $\mathbb{R}$ . Cela inclut non seulement $\Omega_U$ , mais aussi d'autres classes de nombres non calculables, tels que le développement binaire de l'ensemble d'arrêt, les limites de suites de Specker et les réels aléatoires au sens de Martin-Löf.

Signification et affirmations
L'article prétend combler une lacune théorique spécifique laissée par le travail original d'Odrzywo lek en fournissant un théorème formel d'inexpressibilité pour le système EML. La signification réside dans la caractérisation du système EML non seulement comme un outil pour générer des fonctions élémentaires, mais comme un système strictement borné par la calculabilité.

Les auteurs présentent modestement le résultat comme une limitation formelle : bien que l'EML soit esthétiquement plaisant et utile pour le calcul symbolique et l'arithmétique exacte (comme noté dans l'introduction concernant les systèmes de calcul formel), il ne peut pas exprimer les réels non calculables « canoniques ». L'article ne propose pas de nouvelles applications ou de propositions expérimentales ; il sert plutôt de preuve fondamentale établissant que $EML_{\mathbb{R}} \subsetneq \mathbb{R}$ et, plus spécifiquement, que $EML_{\mathbb{R}} \subseteq \text{Comp}_{\mathbb{R}}$ . Le résultat confirme que les nombres « sous forme fermée » expressibles via cet unique opérateur sont strictement limités au domaine des nombres calculables.