Goodstein函数

古德斯坦函数(Goodstein Function)是由鲁宾•古德斯坦(Reuben Goodstein)构造出的快速增长的函数。

定义

首先需要定义数m的以n为底的遗传记法：

假设我们将一个非负整数m表示为n的幂次之和，然后将这些幂指数本身也表示为类似的幂次和，不断重复这一过程，直到所有的最高次指数都小于n。例如，我们可以将100写作$2^6+2^5+2^2$进一步可以写为$2^{2^2+2}+2^{2^2+1}+2^2$。这种表示方式称为m的以n为底的遗传记法。

Goodstein定义了一个数列$G_k(n)$：

对任意自然数n，都有$G_0(n)=n$

对任意自然数n,k，都有$G_{k+1}(n)$是把$G_k(n)$写成以k+2为底的遗传记法，随后把里面所有的k+2改成k+3，最后再把整个数减一所得到的数。

我们拿100作为例子：

$G_0(100)=100=2^{2^2+2}+2^{2^2+1}+2^2$

$G_1(100)=3^{3^3+3}+3^{3^3+1}+3^3-1=3^{3^3+3}+3^{3^3+1}+3^2\times 2+3\times 2+2=228767924549636$

$G_2(100)=4^{4^4+4}+4^{4^4+1}+4^2\times 2+4\times 2+1\approx 3.486030062\times 10^{156}$

……

这种快速增长的序列称为 Goodstein 序列。令人惊讶的是，对于 n 的所有值，$G_k(n)$ 最终达到峰值、下降并返回零。这个事实被称为古德斯坦定理。更令人惊讶的是，可以证明古德斯坦定理无法用皮亚诺算术来证明。

我们定义古德斯坦函数$G(x)$等于古德斯坦序列$G_k(x)=0$时k的值。它的FGH增长率为${\epsilon }_0$.

例子

我们以较小的x作为例子，来计算一下$G(x)$.为了更加清晰，我们不展示$G_k(n)$ 的具体值，而是展示它的以k+2为底的遗传记法表示。读者可以自行计算取值。

x=1

k	$G_k(x)$以k+2为底的遗传记法表示
0	1
1	0

因此G(1)=1.

x=2

k	$G_k(x)$以k+2为底的遗传记法表示
0	2
1	2
2	1
3	0

因此G(2)=3.

x=3

k	$G_k(x)$以k+2为底的遗传记法表示
0	2+1
1	3
2	3
3	2
4	1
5	0

因此G(3)=5.

从G(4)开始，古德斯坦函数将开始“起飞”

x=4

k	$G_k(x)$以k+2为底的遗传记法表示
0	$2^2$
1	$3^2\times 2+3\times 2+2$
2	$4^2\times 2+4\times 2+1$
3	$5^2\times 2+5\times 2$
4	$6^2\times 2+6+5$
9	$11^2\times 2+11$
10	$12^2\times 2+11$
21	$23^2\times 2$
22	$24^2+24\times 23+23$
45	$47^2+47\times 23$
46	$48^2+48\times 22+47$
93	$95^2+95\times 22$
189	$191^2+191\times 21$
381	$383^2+383\times 20$
402653181=$3\times 2^{27}-3$	$402653183^2$
402653182	$402653184\times 402653183+402653183$
$3\times 2^{402653210}-3$	$3\times 2^{402653210}-1$
$3\times 2^{402653210}-2$	$3\times 2^{402653210}-1$
$3\times 2^{402653211}-3$	0

因此$G(4)=3\times 2^{402653211}-3$

这里它展示了很清晰的“下降”过程。

我们有G(12)大于葛立恒数这个结论。

与HH的关系

（待续）