查看“︁Goodstein函数”︁的源代码

古德斯坦函数(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]]的关系 ==
（待续）
[[分类:记号]]