Goodstein函数：修订间差异

2025年7月12日 (六) 10:05的版本

古德斯坦函数(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 1 0^{156}$

……

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

我们定义古德斯坦函数 $G (x)$ 等于古德斯坦序列 $G_{k} (x) = 0$ 时k的值。

例子

我们以较小的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	$1 1^{2} \times 2 + 11$
10	$1 2^{2} \times 2 + 11$
21	$2 3^{2} \times 2$
22	$2 4^{2} + 24 \times 23 + 23$
45	$4 7^{2} + 47 \times 23$
46	$4 8^{2} + 48 \times 22 + 47$
93	$9 5^{2} + 95 \times 22$
189	$19 1^{2} + 191 \times 21$
381	$38 3^{2} + 383 \times 20$
402653181= $3 \times 2^{27} - 3$	$40265318 3^{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的关系

（待续）

@@ 第1行： / 第1行： @@
 古德斯坦函数(Goodstein Function)是由鲁宾•古德斯坦(Reuben Goodstein)构造出的快速增长的函数。
+== 定义 ==
+首先需要定义数m的以n为底的遗传记法：
+假设我们将一个非负整数m表示为n的幂次之和，然后将这些幂指数本身也表示为类似的幂次和，不断重复这一过程，直到所有的最高次指数都小于n。例如，我们可以将100写作<math>2^6+2^5+2^2</math>进一步可以写为<math>2^{2^2+2}+2^{2^2+1}+2^2</math>。这种表示方式称为m的以n为底的遗传记法。
+Goodstein定义了一个数列<math>G_k(n)</math>：
+对任意自然数n，都有<math>G_0(n)=n</math>
+对任意自然数n,k，都有<math>G_{k+1}(n)</math>是把<math>G_k(n)</math>写成以k+2为底的遗传记法，随后把里面所有的k+2改成k+3，最后再把整个数减一所得到的数。
+我们拿100作为例子：
+<math>G_0(100) = 100 = 2^{2^2+2}+2^{2^2+1}+2^2</math>
+<math>G_1(100) = 3^{3^3+3}+3^{3^3+1}+3^3-1 =3^{3^3+3}+3^{3^3+1}+3^2\times2+3\times2+2= 228767924549636</math>
+<math>G_2(100) =4^{4^4+4}+4^{4^4+1}+4^2\times2+4\times2+1\approx3.486030062 \times 10^{156}</math>
+……
+这种快速增长的序列称为 Goodstein 序列。令人惊讶的是，对于 ''n'' 的所有值，<math>G_k(n)</math> 最终达到峰值、下降并返回零。这个事实被称为'''古德斯坦定理'''。更令人惊讶的是，可以证明古德斯坦定理无法用皮亚诺算术来证明。
+我们定义古德斯坦函数<math>G(x)</math>等于古德斯坦序列<math>G_k(x)=0</math>时k的值。
+== 例子 ==
+我们以较小的x作为例子，来计算一下<math>G(x)</math>.为了更加清晰，我们不展示<math>G_k(n)</math> 的具体值，而是展示它的以k+2为底的遗传记法表示。读者可以自行计算取值。
+{| class="wikitable mw-collapsible mw-collapsed"
+|+x=1
+!k
+!<math>G_k(x)</math>以k+2为底的遗传记法表示
+|-
+|0
+|1
+|-
+|1
+|0
+|}
+因此G(1)=1.
+{| class="wikitable mw-collapsible mw-collapsed"
+|+x=2
+!k
+!<math>G_k(x)</math>以k+2为底的遗传记法表示
+|-
+|0
+|2
+|-
+|1
+|2
+|-
+|2
+|1
+|-
+|3
+|0
+|}
+因此G(2)=3.
+{| class="wikitable mw-collapsible mw-collapsed"
+|+x=3
+!k
+!<math>G_k(x)</math>以k+2为底的遗传记法表示
+|-
+|0
+|2+1
+|-
+|1
+|3
+|-
+|2
+|3
+|-
+|3
+|2
+|-
+|4
+|1
+|-
+|5
+|0
+|}
+因此G(3)=5.
+从G(4)开始，古德斯坦函数将开始“起飞”
+{| class="wikitable mw-collapsible mw-collapsed"
+|+x=4
+!k
+!<math>G_k(x)</math>以k+2为底的遗传记法表示
+|-
+|0
+|<math>2^2</math>
+|-
+|1
+|<math>3^2\times2+3\times2+2</math>
+|-
+|2
+|<math>4^2\times2+4\times2+1</math>
+|-
+|3
+|<math>5^2\times2+5\times2</math>
+|-
+|4
+|<math>6^2\times2+6+5</math>
+|-
+|9
+|<math>11^2\times2+11</math>
+|-
+|10
+|<math>12^2\times2+11</math>
+|-
+|21
+|<math>23^2\times2</math>
+|-
+|22
+|<math>24^2+24\times23+23</math>
+|-
+|45
+|<math>47^2+47\times23</math>
+|-
+|46
+|<math>48^2+48\times22+47</math>
+|-
+|93
+|<math>95^2+95\times22</math>
+|-
+|189
+|<math>191^2+191\times21</math>
+|-
+|381
+|<math>383^2+383\times20</math>
+|-
+|402653181=<math>3\times2^{27}-3</math>
+|<math>402653183^2</math>
+|-
+|402653182
+|<math>402653184\times402653183+402653183</math>
+|-
+|<math>3\times2^{402653210}-3</math>
+|<math>3\times2^{402653210}-1</math>
+|-
+|<math>3\times2^{402653210}-2</math>
+|<math>3\times2^{402653210}-1</math>
+|-
+|<math>3\times2^{402653211}-3</math>
+|0
+|}
+因此<math>G(4)=3\times2^{402653211}-3</math>
+这里它展示了很清晰的“下降”过程。
+我们有G(12)大于[[葛立恒数]]这个结论。
+== 与[[HH]]的关系 ==
+（待续）
 [[分类:记号]]