グッドスタイン数列

グッドスタイン数列
型	組合せ数学
急増加関数	\(f_{\epsilon_0}(n)\)

グッドスタイン数列 (Goodstein sequence) は、以下のように定義される整数の数列 G_k(n) で、これは非常に急速に増加する関数となる。

定義

非負整数 n を k の冪乗の和として書き、k の指数部をまた同様に k の冪乗の和として書き、という操作を、すべての指数が k 以下となるまで続ける。たとえば、n=100, k=2 として、100 = 2⁶ + 2⁵ + 2² = 2^{22 + 2} + 2^{22 + 1} + 2² と書くことができる。このとき、これを n のk を底とした遺伝的記法と言う。

上記の 100 の遺伝的記法について、底の 2 に 1 を足して 3 として、異なる数字 3^{33 + 3} + 3^{33 + 1} + 3³ を作成する。この、より大きい数字を B[2](100) と書き、一般には、B[b](n) は、n の b を底とした遺伝的記法において、底を 1 増やす操作をすることを示すものとする。

ここで、帰納的に数列 G₀(n) = n と G_k(n) = B[k + 1](G_{k - 1}(n)) - 1 を定義することができる。すなわち、 k を増加させるごとに、遺伝的記法の底に 1 を足して、計算された数から 1 を引くのである。これは、次のように計算される。

G₀(100) = 100 = 2^{22 + 2} + 2^{22 + 1} + 2²

G₁(100) = B[2](100) - 1 = 3^{33 + 3} + 3^{33 + 1} + 3³ - 1 = 228767924549636

G₂(100) = B[3](G₁(100)) - 1 = 4^{44 + 4} + 4^{44 + 1} + 2 x 4² + 2 x 1 - 1 = 3.486030062 x 10¹⁵⁶

この急速に増加する関数は、グッドスタイン数列として知られている。驚くことに、すべての n に対して、G_k(n) はやがて最大値に到達し、減少し、最後には 0 になるのである。この事実は、グッドスタインの定理として知られている。さらに驚くことに、グッドスタインの定理はペアノ算術によって証明不可能であることが証明できるのである。

証明不可能の証明

初項\(n\)のグッドスタイン数列が0に到達するまでのステップ数を\(G(n)\)とおく。正確には、\(G_k(n) = 0\)を満たす最小の\(k\)に対して\(G(n)=k+1\) とする（\(G_0(n)\)からスタートするので、1を足す。英語版の定義とは異なるが、文献にあわせてこのようにする）。この\(G(n)\)は急速に増大する関数である。

自然数nを底bの遺伝的記法で書き、そこに現われるbをすべてωに置き換えて得られる順序数を、\(R^\omega_b (n)\)とする。例えば、

\[R^\omega_2 (100) = R^\omega_2 (2^{2^2 + 2} + 2^{2^2 + 1} + 2^2) = \omega^{\omega^\omega + \omega} + \omega^{\omega^\omega + 1} + \omega^\omega\]

このときG(n)をハーディー階層により表わすと、 \(G(n) = H_{R^\omega_2 (n)} (3) - 2\)なので、\(G(2 \uparrow\uparrow n) = H_{\varepsilon_0} (n)-2\)が成り立つ。よってG(n)はJonathan Bowersのテトレーション配列と同程度の速さで増大することがわかる。この関数はペアノ算術における任意の可証再帰関数よりも速く増大するので、グッドスタインの定理はペアノ算術では証明不可能である。

計算プログラム

#include <math.h>
#include <stdio.h>
long b, e, k, z = 1;
long u(long n) {
  long i = -1, o = 1;
  while (i++, o * b <= n) o *= b;
  if (i*log10(b+1)>7) n=0, e=1;
  return n ? pow(b + 1, u(i)) + u(n - o) : n;
}

int main() {
  while (z<33) {
    b=1; e=0; k=z++; printf ("G(%ld): ",k-1);
    while (b++, printf ("%ld, ",k-1), fflush (stdout), k = u(--k));
    if (e) printf ("...\n"); else printf ("fin. %ld steps.\n",b-2);
  }
}

\(G(n)\) の値の上限と下限

Caicedo (2007) は \(n = 2^{m_1} + 2^{m_2} + \cdots + 2^{m_k} (m_1 > m_2 > \cdots > m_k\) であれば \(G(n) = f_{R_2^\omega(m_1)}(f_{R_2^\omega(m_2)}(\cdots(f_{R_2^\omega(m_k)}(3))\cdots)) - 2\) となることを示した。ここで、\(R_2^\omega(n)\) は \(n\) を2を底とした遺伝的記法で書いて、2を\(\omega\)に変えたものである。

注

• \(^ba\) は、テトレーション
• \(\uparrow\) は、矢印表記
• \(Ack(n)\) は、1変数のアッカーマン関数 (フリードマンの定義)
• \(\lbrace\rbrace\) は、BEAF
• \(f_\alpha(n)\) は、急増加関数

n	下限	G(n)	上限
0	1
1	2
2	4
3	6
4	\(f_3(3)-2 = 3*2^{402653211}-2\)
5	\((10\uparrow\uparrow (10 \uparrow\uparrow (10 \uparrow\uparrow 10^{10^{10^{20}}}))\)	\(f_4(4)-2\)	\(4 \uparrow\uparrow\uparrow 8\)
6	\((10\uparrow^4)^5 (10\uparrow\uparrow\uparrow)^5 (10\uparrow\uparrow)^5 (10 \uparrow)^5 117\)	\(f_6(6)-2\)	\(6 \uparrow^5 12\)
7	\((10 \uparrow^6)^7 (10\uparrow^5)^7 (10 \uparrow^4)^7 (10\uparrow\uparrow\uparrow)^7 (10 \uparrow\uparrow)^7 (10 \uparrow)^7 619\)	\(f_8(8)-2\)	\(8 \uparrow^7 16\)
8	\(Ack (Ack (3 \times 2^{402653211}) \)	\(f_{\omega+1}(3)-2\)	\(\lbrace 3,4,1,2 \rbrace\)
9	\(Ack (Ack (Ack (G(5))))\)	\(f_{\omega+1}(4)-2\)	\(\lbrace 4,5,1,2 \rbrace\)
10	\(Ack^5 (G(6))\)	\(f_{\omega+1}(6)-2\)	\(\lbrace 6,7,1,2 \rbrace\)
11	\(Ack^7 (G(7))\)	\(f_{\omega+1}(8)-2\)	\(\lbrace 8,9,1,2 \rbrace\)
12	\(Ack^{3 \times 2^{402653211}}(3 \times 2^{402653211})\)	\(f_{\omega+1}(f_3(3))-2\)	\(\lbrace G(4),G(4)+1,1,2 \rbrace\)
13	\(Ack^{G(5)}(G(5))\)	\(f_{\omega+1}(f_4(4))-2\)	\(\lbrace G(5),G(5)+1,1,2 \rbrace\)
14	\(Ack^{G(6)}(G(6))\)	\(f_{\omega+1}(f_6(6))-2\)	\(\lbrace G(6),G(6)+1,1,2 \rbrace\)
15	\(Ack^{G(7)}(G(7))\)	\(f_{\omega+1}(f_8(8))-2\)	\(\lbrace G(7),G(7)+1,1,2 \rbrace\)
16	\(\lbrace 3,4,3,3,3 \rbrace\)	\(f_{\omega^3}(3)-2\)	\(\lbrace 3,5,3,3,3 \rbrace\)
17	\(\lbrace 4,5,4,4,4,4 \rbrace\)	\(f_{\omega^4}(4)-2\)	\(\lbrace 4,6,4,4,4,4 \rbrace\)
18	\(\lbrace 6,7,6,6,6,6,6,6 \rbrace\)	\(f_{\omega^6}(6)-2\)	\(\lbrace 6,8,6,6,6,6,6,6 \rbrace\)
19	\(\lbrace 8,9,8,8,8,8,8,8,8,8 \rbrace\)	\(f_{\omega^8}(8)-2\)	\(\lbrace 8,10,8,8,8,8,8,8,8,8 \rbrace\)
20	\(\lbrace G(4),G(4)+2 (1) 2 \rbrace\)	\(f_{\omega^\omega}(f_3(3))-2\)	\(\lbrace G(4),G(4)+3 (1) 2 \rbrace\)
32	\(\lbrace 3,4,2 (1) 2 \rbrace\)	\(f_{\omega^\omega+1}(3)-2\)	\(\lbrace 3,5,2 (1) 2 \rbrace\)
64	\(\lbrace 3,4,4 (1) 2 \rbrace\)	\(f_{\omega^\omega+3}(3)-2\)	\(\lbrace 3,5,4 (1) 2 \rbrace\)
128	\(\lbrace 3,4,1,2 (1) 2 \rbrace\)	\(f_{\omega^\omega+\omega+1}(3)-2\)	\(\lbrace 3,5,1,2 (1) 2 \rbrace\)
256	\(\lbrace 3,5 (1) 3 \rbrace\)	\(f_{(\omega^\omega)3}(3)-2\)	\(\lbrace 3,6 (1) 3 \rbrace\)
65536	\(\lbrace 3,3 (3) 2 \rbrace\)	\(f_{\omega^{\omega^3}}(3)-2\)	\(\lbrace 3,4 (3) 2 \rbrace\)
65540	\(\lbrace 3,3 (G(4)) 2 \rbrace\)	\(f_{\omega^{\omega^\omega}}(f_3(3))-2\)	\(\lbrace 3,3 (G(4)+1) 2 \rbrace\)
\(2^{65536}\)	\(\lbrace 3,3 (3,3,3,2) 3 \rbrace\)	\(f_{\omega^{\omega^{\omega^3}}}(3)-2\)	\(\lbrace 3,4 ((1) 2) 2 \rbrace\)
\(2^{65536}+4\)	\(\lbrace 3,G(4) ((1) 2) 2 \rbrace\)	\(f_{\omega^{\omega^{\omega^\omega}}}(f_3(3))-2\)	\(\lbrace 3,G(4)+1 ((1) 2) 2 \rbrace\)
\(^n2\)	\(^{n-2}3 \& 3\)	\(f_{^{n-1}\omega}(3)-2\)	\(^{n-1}3 \& 3\)

弱いグッドスタイン数列

遺伝的記法の代わりに通常の基底表記を用いても、グッドスタインの定理は成り立つ。ここで、このときグッドスタイン数列と同じように定義できる数列を弱いグッドスタイン数列\(g(n)\)とする。

グッドスタイン数列と同様、\(g(n)\)もハーディー関数を用いて計算できる。大体急増加関数では\(f_{\omega}(n)\)、矢印表記では\(2 \uparrow^{n-1} n\)と表せる。

n	g(n)の下限	g(n)の上限
0	0
1	1
2	3
3	5
4	21
5	61
6	381
7	2045
8	\(3 \times 2^{402653211}-3\)
9	\(10^{2.0756 \times 10^{121210694}}\)	\(10^{2.0757 \times 10^{121210694}}\)
10	\(10^{10^{10^{2.0756 \times 10^{121210694}}}}\)	\(10^{10^{10^{2.0757 \times 10^{121210694}}}}\)
11	\(10^{10^{10^{10^{10^{2.0756 \times 10^{121210694}}}}}}\)	\(10^{10^{10^{10^{10^{2.0757 \times 10^{121210694}}}}}}\)
12	\(10 \uparrow\uparrow 23\)	\(10 \uparrow\uparrow 24\)
13	\(10 \uparrow\uparrow 63\)	\(10 \uparrow\uparrow 64\)
14	\(10 \uparrow\uparrow 383\)	\(10 \uparrow\uparrow 384\)
15	\(10 \uparrow\uparrow 2047\)	\(10 \uparrow\uparrow 2048\)
16	\((10 \uparrow\uparrow)^{2} (g(4)+2)\)	\((10 \uparrow\uparrow)^{2} (g(4)+3)\)
17	\((10 \uparrow\uparrow)^{3} (g(5)+2)\)	\((10 \uparrow\uparrow)^{3} (g(5)+3)\)
18	\((10 \uparrow\uparrow)^{5} (g(6)+2)\)	\((10 \uparrow\uparrow)^{5} (g(6)+3)\)
19	\((10 \uparrow\uparrow)^{7} (g(7)+2)\)	\((10 \uparrow\uparrow)^{7} (g(7)+3)\)
20	\(10 \uparrow\uparrow\uparrow 24\)	\(10 \uparrow\uparrow\uparrow 25\)
32	\((10 \uparrow\uparrow\uparrow)^{3} (g(8)+3)\)	\((10 \uparrow\uparrow\uparrow)^{3} (g(8)+4)\)
64	\((10 \uparrow\uparrow\uparrow\uparrow)^{3} (g(16)+3)\)	\((10 \uparrow\uparrow\uparrow\uparrow)^{3} (g(16)+4)\)
\(2^n\)	\(2 \uparrow^{n-1} n\)	\(2 \uparrow^n n\)