查看“︁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的值。它的FGH增长率为<math>\varepsilon_0</math>.

== 例子 ==
我们以较小的x作为例子，来计算一下<math>G(x)</math>.为了更加清晰，我们不展示<math>G_k(n)</math> 的具体值，而是展示它的以k+2为底的遗传记法表示。读者可以自行计算取值。
{| class="wikitable mw-collapsible mw-collapsed" style="1"
|+x=1<div style="display:inline;opacity:0;height:0;">aaaaa</div>
!k
!<math>G_k(x)</math>以k+2为底的遗传记法表示
|-
|0
|1
|-
|1
|0
|}
因此G(1)=1.
{| class="wikitable mw-collapsible mw-collapsed"
|+x=2<div style="display:inline;opacity:0;height:0;">aaaaa</div>
!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<div style="display:inline;opacity:0;height:0;">aaaaa</div>
!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<div style="display:inline;opacity:0;height:0;">aaaaa</div>
!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]] 的关系 ==
定义<math>R^\omega_a(n)</math>为将n表示为以a为底的遗传记法，然后将所有的底数a全部替换为<math>\omega</math>所得到的序数。我们可以证明以下结论：

<math>G(n)=H_{R^\omega_2(n)}(3)-3</math>，其中<math>H_\alpha(n)</math>是 [[增长层级#哈代层级|Hardy 层级]]。

=== 证明 ===
以下叙述中总是考虑带乘法的[[康托范式]]和小于<math>\varepsilon_0</math>的序数，希腊字母表示序数，拉丁字母表示正整数。

先证一个引理：'''<math>H_{R^\omega_a(b+1)}(a)=H_{R^\omega_a(b)+1}(a)</math>，<math>a</math>是不小于3的正整数。'''

引理的证明：以下用<math>k</math>表示某个小于<math>a</math>的正整数。我们称一个序数<math>\alpha</math>是好的，如果它的康托范式中出现的所有正整数全都小于<math>a</math>。不难得出，<math>\alpha</math>是好的当且仅当它是某个<math>R^\omega_a(b)</math>的取值。

记<math>R^\omega_a(b+1)=\alpha</math>。将<math>H_\alpha(a)</math>进行多次取基本列，使下标为后继序数，得到<math>H_\beta(a)</math>。那么：

'''1)  <math>\beta</math>是好的，不考虑正整数项。'''

由于<math>H_\beta(a)</math>的自变量为<math>a</math>，取基本列时得到的正整数不超过<math>a</math>。那么只要证明产生<math>\beta</math>时得到的<math>a</math>会在下一步被立即使用即可：

若<math>\alpha</math>是后继序数，则<math>\alpha=\beta</math>，显然是好的。

若<math>\alpha</math>是极限序数，设<math>\alpha=\alpha_0+\gamma\times{k}</math>：

# <math>\gamma=\omega</math>，则下一步得到<math>\alpha_0+\gamma\times{(k-1)}+a</math>，已经是后继了，故结论成立；
# <math>\gamma=\omega^{\delta+1}</math>，<math>\delta</math>是大于等于1的序数，则下一步得到<math>\alpha_0+\gamma\times{(k-1)}+\omega^\delta\times{a}</math>，下一步取<math>\omega^\delta\times{a}</math>的基本列，故结论成立；
# <math>\gamma=\omega^{\gamma_0+\omega\times{k}}</math>，则下一步得到<math>\alpha_0+\omega^{\gamma_0+\omega\times{(k-1)}+a}</math>，下一步取<math>\omega^{\cdots+a}</math>的基本列，故结论成立；
# <math>\gamma=\omega^{\gamma_0+\sigma\times{k}}</math>，<math>\sigma</math>是<math>\omega^2</math>的倍数，则此时等效于对<math>\sigma</math>取两次基本列的问题。由于<math>\sigma<\gamma</math>，使用序数的递降法知结论成立。

以上对于<math>\gamma=\omega^\sigma</math>中分别讨论了<math>\sigma=1</math>，<math>\sigma</math>为非1后继序数，<math>\sigma</math>为极限序数但不为<math>\omega^2</math>的倍数，<math>\sigma</math>为<math>\omega^2</math>的倍数的情况。综上，结论1)得证。

易得<math>g_{R^\omega_a(n)}(a)=n</math>，其中g是SGH。设<math>\beta=\theta+1</math>，则<math>\theta</math>是好的。所以，

由于增长层级在取基本列上规则相同，<math>g_\alpha(a)=g_\beta(a)</math>，

<math>g_{\theta+1}(a)=g_\beta(a)=g_\alpha(a)=b+1=g_{R^\omega_a(b)}(a)+1=g_{R^\omega_a(b)+1}(a)</math>，

<math>g_\theta(a)=g_{R^\omega_a(b)}(a)</math>。

由于<math>\theta</math>是好的，遗传记法是唯一的，故<math>\theta=R^\omega_a(b)</math>。从而<math>H_{R^\omega_a(b+1)}(a)=H_\alpha(a)=H_\beta(a)=H_{\theta+1}(a)=H_{R^\omega_a(b)+1}(a)</math>。引理得证。

'''原命题的证明'''    对于一般的自然数<math>k</math>，根据Goodstein序列的定义，有<math>R^\omega_{k+3}(G_{k+1}(n)+1)=R^\omega_{k+2}(G_k(n))</math>。于是，

<math>H_{R^\omega_{k+3}(G_{k+1}(n))}(k+4)=H_{R^\omega_{k+3}(G_{k+1}(n))+1}(k+3)</math>，

使用引理，

<math>=H_{R^\omega_{k+3}(G_{k+1}(n)+1)}(k+3)=H_{R^\omega_{k+2}(G_k(n))}(k+3)</math>。

于是，<math>H_{R^\omega_{k+2}(G_k(n))}(k+3)</math>是与<math>k</math>无关的常数。分别令<math>k=G(n)</math>，<math>k=0</math>，得到

<math>G(n)+3=H_0(G(n)+3)=H_{R^\omega_{G(n)+2}(0)}(G(n)+3)=H_{R^\omega_2(n)}(3)</math>，从而证明了

<math>G(n)=H_{R^\omega_2(n)}(3)-3</math>。

== 枚举 ==

有了刚刚的结论，我们可以快速地求出一些Goodstein函数的值。以下使用[[增长层级#快速增长层级|FGH]]，并且利用了结论<math>H_{\omega^\alpha}(n)=f_{\alpha}(n)</math>：

<math>G(0)=0</math>

<math>G(1)=1</math>

<math>G(2)=3</math>

<math>G(3)=5</math>

<math>G(4)=f_3(3)-3</math>

<math>G(5)=f_5(4)-3</math>

<math>G(6)=f_6(6)-3</math>

<math>G(7)=f_8(8)-3</math>

<math>G(8)=f_{\omega+1}(3)-3</math>

<math>G(9)=f_{\omega+1}(4)-3</math>

<math>G(10)=f_{\omega+1}(6)-3</math>

<math>G(11)=f_{\omega+1}(8)-3</math>

<math>G(12)=f_{\omega+1}(f_3(3))-3</math>

<math>G(13)=f_{\omega+1}(f_4(4))-3</math>

<math>G(14)=f_{\omega+1}(f_6(6))-3</math>

<math>G(15)=f_{\omega+1}(f_8(8))-3</math>

<math>G(16)=f_{\omega^3}(3)-3</math>

<math>G(17)=f_{\omega^4}(4)-3</math>

<math>G(18)=f_{\omega^6}(6)-3</math>

<math>G(19)=f_{\omega^8}(8)-3</math>

<math>G(20)=f_{\omega^\omega}(f_3(3))-3</math>

<math>\cdots</math>

一般地，我们有

<math>G(2\uparrow\uparrow{n})=f_{\omega\uparrow\uparrow(n-1)}(3)-3</math>。

据此可以得到，Goodstein函数的增长率为<math>\varepsilon_0</math>。

{{默认排序:相关问题}}
[[分类:记号]]