Sudan 函数

苏丹函数(Sudan function)是由罗马尼亚数学家 Gabriel Sudan 创造的递归但非原始递归的全可计算函数，是历史上首个公开发表的非原始递归函数，其发表时间（1927年）早于广为人知的阿克曼函数（1928年）。该函数与阿克曼函数在计算能力上等价，同为可计算理论与递归论中证明“可计算函数集严格大于原始递归函数集”的核心反例，同时也是大数数学中刻画超指数增长的经典函数。

一般定义

定义

现代通用的苏丹函数标准定义为三元递归函数，记为 $F_{n} (x, y)$ （亦写作 $F (n, x, y)$ ），其定义域为全体非负整数 $n, x, y \in ℕ$ ，递归规则如下^[1]^[2]：

$F_{n} (x, y) = {\begin{cases} x + y & , n = 0 \\ x & , n > 0 and y = 0 \\ F_{n - 1} (F_{n} (x, y - 1), F_{n} (x, y - 1) + y) & , n > 0 and y > 0 \end{cases}$

注：部分文献中会将递归式的末项写作 $F_{n} (x, y - 1) + y + 1$ ，属于等价的变体定义，仅会导致低阶函数的闭式解出现常数偏移，不改变函数的核心增长特性与非原始递归性。

在该标准定义下，苏丹函数的FGH增长率约为 $ω$ ，与罗宾逊版本的阿克曼函数增长层级等价。

低阶展开与闭式解

苏丹函数的每一层级 $n$ 对应着远超上一层级的增长速度，低阶层级可推导出显式闭式解，直观展现其增长特性：

1. 0阶苏丹函数（加法） $F_{0} (x, y) = x + y$ 对应基础的加法运算，为线性增长。

2. 1阶苏丹函数由递归规则展开： $F_{1} (x, 0) = x F_{1} (x, y) = F_{0} (F_{1} (x, y - 1), F_{1} (x, y - 1) + y) = 2 \cdot F_{1} (x, y - 1) + y$ 通过线性非齐次递推关系求解，可得其闭式解： $F_{1} (x, y) = 2^{y} \cdot x + (2^{y + 1} - y - 2)$

3. 2阶苏丹函数递归规则为： $F_{2} (x, 0) = x F_{2} (x, y) = F_{1} (F_{2} (x, y - 1), F_{2} (x, y - 1) + y)$ 代入1阶闭式解可得其递归展开式： $F_{2} (x, y) = 2^{F_{2} (x, y - 1) + y} \cdot F_{2} (x, y - 1) + (2^{F_{2} (x, y - 1) + y + 1} - (F_{2} (x, y - 1) + y) - 2)$

4. n≥3阶苏丹函数随着阶数n的提升，苏丹函数的增长速度依次进入迭代幂次、迭代塔级等更高阶的超运算范畴，其增长速度与同阶的阿克曼函数相当。

计算示例

这里以标准定义为基础，完整展开低阶苏丹函数的计算过程，直观展现其递归逻辑：

示例1：计算 $F_{1} (2, 3)$

$\begin{array}{lll} F_{1} (2, 3) & = & F_{0} (F_{1} (2, 2), F_{1} (2, 2) + 3) \\ = & 2 \cdot F_{1} (2, 2) + 3 \\ = & 2 \cdot [2 \cdot F_{1} (2, 1) + 2] + 3 \\ = & 4 \cdot F_{1} (2, 1) + 7 \\ = & 4 \cdot [2 \cdot F_{1} (2, 0) + 1] + 7 \\ = & 8 \cdot F_{1} (2, 0) + 11 \\ = & 8 \times 2 + 11 \\ = & 27 \end{array}$

代入闭式解验证： $F_{1} (2, 3) = 2^{3} \times 2 + (2^{4} - 3 - 2) = 16 + 11 = 27$ ，与递归展开结果一致。

示例2：计算 $F_{2} (1, 2)$

$\begin{array}{lll} F_{2} (1, 2) & = & F_{1} (F_{2} (1, 1), F_{2} (1, 1) + 2) \\ = & F_{1} (F_{1} (F_{2} (1, 0), F_{2} (1, 0) + 1), F_{1} (F_{2} (1, 0), F_{2} (1, 0) + 1) + 2) \\ = & F_{1} (F_{1} (1, 1 + 1), F_{1} (1, 1 + 1) + 2) \\ = & F_{1} (F_{1} (1, 2), F_{1} (1, 2) + 2) \\ = & F_{1} (2^{2} \times 1 + 2^{3} - 2 - 2, 2^{2} \times 1 + 2^{3} - 2 - 2 + 2) \\ = & F_{1} (8, 10) \\ = & 2^{10} \times 8 + 2^{11} - 10 - 2 \\ = & 8192 + 2048 - 12 \\ = & 10228 \end{array}$

函数值表

标准定义下 $F_{n} (x, y)$ 的函数值表
阶数n \ x\y	0	1	2	3	4	通式
0	0	1	2	3	4	$x + y$
	1	2	3	4	5
	2	3	4	5	6
	3	4	5	6	7
	4	5	6	7	8
1	0	2	6	15	34	$2^{y} \cdot x + 2^{y + 1} - y - 2$
	1	3	8	19	42
	2	5	12	27	58
	3	7	16	35	74
	4	9	20	43	90
2	0	2	26	极大值	无法用常规数值表示	超指数塔级增长，无初等闭式解
	1	5	10228	超天文数值	无法用常规数值表示
	2	8	超天文数值	无法用常规数值表示	无法用常规数值表示
	3	11	无法用常规数值表示	无法用常规数值表示	无法用常规数值表示
	4	14	无法用常规数值表示	无法用常规数值表示	无法用常规数值表示
3	增长速度进入迭代超幂范畴，仅极小的x,y取值可计算有限数值，其余均为无法常规表示的超天文大数

其他定义

原始定义

Gabriel Sudan在1927年的原始论文中，以超限序数 $ω^{ω}$ 为背景提出了该函数，原始定义基于更一般的超限递归框架，其核心递归结构与现代标准定义完全一致，仅参数表述略有差异^[3]。原始定义的递归式可表述为： $S (n, x, y) = {\begin{cases} x + y & , n = 0 \\ x & , n > 0 and y = 0 \\ S (n - 1, S (n, x, y - 1), S (n, x, y - 1) + y) & , n > 0 and y > 0 \end{cases}$ 该定义是首个被严格证明的非原始递归函数，为递归论的发展奠定了重要基础。

变体定义（常数偏移版）

部分递归论文中会使用边界值微调的变体定义，其核心递归结构不变，仅将递归式的第二个参数调整为 $F_{n} (x, y - 1) + y + 1$ ，更便于教学演示，定义如下： $F_{n} (x, y) = {\begin{cases} x + y & , n = 0 \\ x & , n > 0 and y = 0 \\ F_{n - 1} (F_{n} (x, y - 1), F_{n} (x, y - 1) + y + 1) & , n > 0 and y > 0 \end{cases}$ 该变体下1阶苏丹函数的递推式简化为 $F_{1} (x, y) = 2 \cdot F_{1} (x, y - 1) + y + 1$ ，闭式解为 $F_{1} (x, y) = 2^{y} (x + 1) - y - 2$ ，其增长层级与非原始递归性与标准定义完全一致。

历史背景

苏丹函数由罗马尼亚数学家Gabriel Sudan于1927年正式发表，他是著名数学家大卫·希尔伯特的学生，与阿克曼为同门师兄弟。

20世纪20年代，希尔伯特在数学基础的研究中提出猜想：所有可计算的全函数均为原始递归函数。为验证该猜想，希尔伯特的学生们展开了对递归函数的系统性研究。1927年，Gabriel Sudan在论文《Sur le nombre transfini $ω^{ω}$ 》中正式提出了苏丹函数，并严格证明了该函数是可计算的全函数，但不属于原始递归函数，成为历史上首个推翻希尔伯特该猜想的反例^[4]。

1928年，同门的Wilhelm Ackermann发表了与之等价的阿克曼函数，因其递归结构更简洁，后续被更广泛地用于递归论与可计算理论的教学与研究中，而苏丹函数则作为首个非原始递归函数，在递归论的发展史上具有里程碑式的开创意义。

核心性质

1. 全可计算性

苏丹函数对所有非负整数输入 $n, x, y$ 均有唯一确定的输出，是定义在 $ℕ^{3}$ 上的全函数，且可通过图灵机、递归程序等计算模型实现有效计算，属于可计算函数的范畴。

2. 非原始递归性

苏丹函数是首个被严格证明的非原始递归函数：它可通过一般递归定义构造，但无法仅通过原始递归函数的核心算子（复合算子、原始递归算子）从本原函数（零函数、后继函数、投影函数）中构造出来。其核心原因在于，苏丹函数的增长速度超过了所有原始递归函数的增长速度上限^[5]。

3. 与阿克曼函数的计算等价性

苏丹函数与阿克曼函数在计算能力上完全等价，二者同属 $ω$ 级快速增长层级，可通过原始递归变换互相转化。二者的核心差异仅在于递归结构的嵌套方式，而非本质的计算能力与增长极限^[6]。

与阿克曼函数的核心对比

苏丹函数与阿克曼函数的核心对比
特征维度	苏丹函数（Sudan Function）	阿克曼函数（Ackermann Function）
发表时间	1927年，历史首个非原始递归函数	1928年，晚于苏丹函数发表
提出者	Gabriel Sudan（希尔伯特的学生）	Wilhelm Ackermann（希尔伯特的学生，与Sudan同门）
标准定义参数	三元递归函数 $F_{n} (x, y)$	主流为罗宾逊简化版二元递归函数 $A (m, n)$ ，原始定义为三元
递归结构	嵌套递归的第二个参数随y动态增长，嵌套复杂度更高	递归结构更简洁，仅对第一个参数做层级递归，第二个参数做嵌套调用
低阶对应运算	n=0对应加法，n=1对应指数级增长	m=0对应后继函数，m=1对应加法，m=2对应乘法，m=3对应指数级增长
学术知名度	较低，多出现于递归论史与大数数学领域	极高，是可计算理论、算法复杂度分析中的标准示例
核心历史地位	首个公开发表的非原始递归函数，推翻希尔伯特猜想的首个反例	最广为人知的非原始递归函数，成为递归论的经典范例
增长层级（FGH）	$ω$ ，与阿克曼函数等价	$ω$ ，与苏丹函数等价

其他内容

增长层级与超运算表示

苏丹函数的增长速度可通过高德纳上箭头表示法进行刻画，其n阶苏丹函数的增长速度对应n+1阶超运算：

$F_{0} (x, y)$ 对应1阶超运算（加法）： $x [1] y$

$F_{1} (x, y)$ 增长速度等价于3阶超运算（指数）： $x [3] y$

$F_{2} (x, y)$ 增长速度等价于4阶超运算（迭代幂次/塔级）： $x [4] y$

一般地， $F_{n} (x, y)$ 的增长速度等价于 $x [n + 2] y$ ，与同阶阿克曼函数的超运算等级一致。

在快速增长层级（FGH）中，苏丹函数的对角化版本 $F (n, n, n)$ 的增长率为 $f_{ω} (n)$ ，与阿克曼函数的对角化版本完全等价。

苏丹数（Sudan Numbers）

类比阿克曼数，我们将苏丹函数的对角化序列称为苏丹数，其定义为： $S_{n} = F_{n} (n, n)$ 其中n为非负整数。苏丹数是对苏丹函数的对角化：

$S_{0} = F_{0} (0, 0) = 0 + 0 = 0$

$S_{1} = F_{1} (1, 1) = 2^{1} \times 1 + 2^{2} - 1 - 2 = 3$

$S_{2} = F_{2} (2, 2) . . .$

逆苏丹函数

类比逆阿克曼函数，我们定义逆苏丹函数为： $σ_{i} (n) = \min {j \in ℕ ∣ F_{i} (j, j) \geq n}$ 该函数是苏丹函数的逆函数，由于苏丹函数的超高速增长特性，逆苏丹函数的增长速度极为缓慢，在算法时间复杂度分析中，可用于刻画极优的渐进复杂度下界，与逆阿克曼函数的应用场景高度相似^[7]。

连续域扩展

与阿克曼函数类似，研究者也提出了苏丹函数在非负实数域上的连续扩展，使其可对实数输入 $n, x, y \in ℝ_{\geq 0}$ 进行定义，核心扩展思路为：

1. 对0阶函数，保持加法的连续定义： $F_{0} (x, y) = x + y$

2. 对非整数阶数与非整数y，通过插值与分段递归的方式，保持函数的单调性与递归结构的一致性

该连续扩展保留了离散苏丹函数的核心增长特性，为其在分析学、动力系统中的应用提供了基础。

参考资料

↑ Calude, C., Marcus, S., & Tevy, I. (1979). "The first example of a recursive function which is not primitive recursive". Historia Mathematica, 6(4), 380-384.
↑ Sudan, G. (1927). "Sur le nombre transfini $ω^{ω}$ ". Bulletin mathématique de la Société Roumaine des Sciences, 30, 11-30.
↑ Sudan, G. (1927). "Sur le nombre transfini $ω^{ω}$ ". Bulletin mathématique de la Société Roumaine des Sciences, 30, 11-30.
↑ Calude, C., Marcus, S., & Tevy, I. (1979). "The first example of a recursive function which is not primitive recursive". Historia Mathematica, 6(4), 380-384.
↑ Kleene, S. C. Introduction to Metamathematics. Princeton, NJ: Van Nostrand, 1964.
↑ Googology Wiki. "Sudan Function". https://googology.fandom.com/wiki/Sudan_function
↑ Tarjan, R. E. Data Structures and Network Algorithms. Philadelphia PA: SIAM, 1983.

[1] Calude, C., Marcus, S., & Tevy, I. (1979). "The first example of a recursive function which is not primitive recursive". Historia Mathematica, 6(4), 380-384.

[2] Sudan, G. (1927). "Sur le nombre transfini $ω^{ω}$ ". Bulletin mathématique de la Société Roumaine des Sciences, 30, 11-30.

[3] Sudan, G. (1927). "Sur le nombre transfini $ω^{ω}$ ". Bulletin mathématique de la Société Roumaine des Sciences, 30, 11-30.

[4] Calude, C., Marcus, S., & Tevy, I. (1979). "The first example of a recursive function which is not primitive recursive". Historia Mathematica, 6(4), 380-384.

[5] Kleene, S. C. Introduction to Metamathematics. Princeton, NJ: Van Nostrand, 1964.

[6] Googology Wiki. "Sudan Function". https://googology.fandom.com/wiki/Sudan_function

[7] Tarjan, R. E. Data Structures and Network Algorithms. Philadelphia PA: SIAM, 1983.

[1]

[2]

[3]

[4]

[5]

[6]

[7]