🔢 mathematics

Inexpressibility in Exp-Minus-Log

本文证明，将初等函数简化为一个常数和一个二元运算的 Exp-Minus-Log 系统仅能表达可计算数，从而证明 Chaitin 的 $\Omega_U$ 在该框架内不可表达。

原作者： Mark Carney

发布于 2026-05-05

📖 1 分钟阅读🧠 深度阅读

原作者： Mark Carney

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你拥有一间神奇且无所不能的厨房。在这间厨房里，你没有像搅拌机、烤箱和搅拌器那样全套的工具。相反，你只有一件特殊工具，我们称之为“魔法魔杖”（在论文中表示为E），以及一种单一原料：数字1。

马克·卡尼的这篇论文探讨了如果仅使用这根魔杖和这一种原料，试图烹饪出所有可能的数字会发生什么。

魔法魔杖的食谱

魔杖以一种非常特定的方式运作。如果你将它指向两样东西，比如A和B，它会施展一个特定的戏法：它取 A 的指数（一种让它飞速增长的华丽方式），然后减去 B 的对数（一种让它缩小的方式）。

公式：结果 = exp(A) - log(B)

原始研究人员（Odrzywo lek）证明，仅凭这一戏法和数字 1，你实际上可以重现几乎所有我们通常认为是“标准数学”的内容。你可以构建整数、分数、数字 $\pi$ 、 $e$ ，甚至像正弦和余弦这样的复杂函数。这就像仅用一把勺子和一杯面粉就能烘焙出整个婚礼蛋糕。

核心问题：你能烹饪出一切吗？

这篇论文提出了一个更深层的问题：这间厨房是否有什么东西是无法制作的？

为了回答这个问题，作者将这间“魔法魔杖”厨房与一组已知的数字进行了比较，这组数字被称为EL 数（以数学家蒂莫西·肖的名字命名）。论文证明，魔法魔杖厨房和肖的厨房实际上是同一个地方。它们能制作出完全相同的数字列表。

“不可烹饪”的原料：查廷的 $\Omega$

随后，作者引入了一种非常奇特、理论性的原料，称为查廷的 $\Omega$ （欧米伽）。

它是什么？ 想象一个代表计算机程序停止（停机）或无限运行的概率的数字。
它为何特殊？ 这个数字是“不可计算的”。它不仅仅是一个我们尚未计算出的数字；从数学上讲，任何计算机（无论多么强大）都不可能写出它的精确位数或预测它的下一位数字。它是一个存在的数字，但在根本上，任何逐步的食谱都无法“触及”它。

主要发现

论文证明了一条简单而有力的规则：你能用魔法魔杖制作出的每一个数字都是“可计算的”。

以下是用通俗英语阐述的逻辑：

原料是安全的：你从数字 1 开始（这很容易计算）。
过程是安全的：魔法魔杖只做两件事：exp 和 log。论文表明，如果你将这些工具输入给计算机可以计算的数字，它们输出的结果计算机也同样可以计算。
结论：既然你从一个可计算的数字开始，并且只使用可计算的工具，那么在这个系统中你能构建的每一个数字都必须是可计算的。

由于查廷的 $\Omega$ 不可计算，因此不可能在这间厨房里构建出它。

最终裁决

论文以“形式不可表达性定理”作为结论。简单来说：

魔法魔杖厨房可以制作一个巨大且无限的数字列表（包括 $\pi$ 、 $e$ 以及工程和物理学中使用的所有数字）。
然而，有一片广阔的数字海洋是这间厨房永远无法触及的。
查廷的 $\Omega$ 是这些不可触及数字的“典型代表”。它是一个具体的证明，表明存在某些数学真理，无法使用这套特定的规则系统来表达。

一个简单的类比

将魔法魔杖系统想象成一个只有红色积木的乐高套装。

你可以建造一座房子、一辆车、一座城堡或一艘宇宙飞船（这些是像 $\pi$ 和 $e$ 这样的“可计算”数字）。
但如果有人要求你建造一块蓝色积木，你做不到。无论你堆叠多少红色积木，你永远无法创造出一块蓝色的。
查廷的 $\Omega$ 就是那块“蓝色积木”。它存在于数学宇宙中，但它是由一种材料（不可计算性）构成的，这种材料根本无法使用你手中可用的红色积木（EML 系统）来构建。

总之：论文证实，虽然这个单函数系统极其强大，涵盖了我们在日常生活和科学中使用的几乎所有数字，但它有一个硬性限制。它无法触及“不可计算”的数字，证明某些数学概念对于这种特定的书写方式来说，永远是遥不可及的。

技术摘要：Exp-Minus-Log 系统中的不可表达性

问题陈述
本文旨在填补 Odrzywo lek [4] 最初定义的 Exp-Minus-Log（EML）系统在理论理解上的空白。该系统将所有复数上的初等函数、常数和运算归约为单一二元运算符 $E(\alpha, \beta) = \exp(\alpha) - \log(\beta)$ 以及常数"1"。尽管 Odrzywo lek 的工作主要是构造性和存在性的——展示了如何表达标准初等函数——但并未建立形式化的不可表达性定理。具体而言，EML 系统是否能够表达非可计算实数，此前仍是一个未解之谜。本文旨在通过确定系统内所有可表示数字的可计算性状态，来刻画 EML 表达能力的界限。

方法论
作者结合形式逻辑、可计算分析以及算法信息论，确立了 EML 的边界。该方法论按三个逻辑阶段推进：

形式等价性：本文首先建立了 Odrzywo lek 的 EML 数与 Chow 的 EL 数 [2] 之间的严格等价关系。通过提供显式的句法替换，作者证明了 EML 数域与 EL 数域（在 $\exp$ 和 $\log$ 下封闭的 $\mathbb{C}$ 的最小子域）是相同的。
可计算性分析：利用可计算分析的结果（特别是 [7] 和 [6]），作者分析了所涉及运算的可计算性。他们利用了指数函数在所有可计算复数输入上均可计算这一事实。对于对数函数，作者通过证明对于任何已定义的 EML 表达式，其对数参数要么位于负实轴上（此时可通过模长和 $\pi$ 计算其值），要么与分支割线保持有理距离，从而解决了分支割线问题。
可计算性的归纳证明：通过对 EML 表达式的句法进行结构归纳，作者证明了每一个已定义的 EML 表达式都求值为一个可计算复数。
见证选择：为了证明不可表达性，本文利用 Chaitin 的 $\Omega_U$ （通用前缀自由图灵机的停机概率）作为标准见证。已知 $\Omega_U$ 是左可枚举的，但不可计算。

主要贡献与结果
本文得出以下主要结果：

等价定理：证明了 EML 可表达数的集合恰好等于 Chow 的 EL 数集合（$EML = EL$）。
可计算性定理：本文证明了每一个 EML 可表达数都是可计算的。具体而言，对于任何值已定义的闭 EML 表达式 $\phi$ ， $[[\phi]]$ 是一个可计算复数。因此，EML 可构造实数集（ $EML_{\mathbb{R}}$ ）是可计算实数集（ $\text{Comp}_{\mathbb{R}}$ ）的子集。
不可表达性定理：通过将 EML 数的可计算性与 Chaitin 的 $\Omega_U$ 的不可计算性相结合，本文形式化地证明了 $\Omega_U \notin EML_{\mathbb{R}}$ 。
测度论推论：由于 EML 数集是可数的（源于句法的可数性），非 EML 可表达实数集在 $\mathbb{R}$ 上具有满勒贝格测度。这不仅包括 $\Omega_U$ ，还包括其他类别的非可计算数，例如停机集的二进制展开、Specker 序列的极限以及 Martin-Löf 随机实数。

意义与主张
本文声称通过为 EML 系统提供形式化的不可表达性定理，填补了 Odrzywo lek 原始工作留下的特定理论空白。其意义在于将 EML 系统不仅刻画为生成初等函数的工具，更刻画为一个严格受限于可计算性的系统。

作者谦逊地将该结果表述为一种形式化局限：尽管 EML 在美学上令人愉悦，且对符号计算和精确算术（正如引言中关于计算机代数系统 CAS 所述）很有用，但它无法表达“标准的”非可计算实数。本文并未提出新的应用或实验方案；相反，它作为基础证明，确立了 $EML_{\mathbb{R}} \subsetneq \mathbb{R}$ ，更具体地说是 $EML_{\mathbb{R}} \subseteq \text{Comp}_{\mathbb{R}}$ 。该结果证实，通过该单一运算符表达的“闭形式”数严格局限于可计算数的范畴。