| グッドスタイン数列 | |
|---|---|
| 型 | 組合せ数学 |
| 急増加関数 | \(f_{\epsilon_0}(n)\) |
グッドスタイン数列 (Goodstein sequence) は、以下のように定義される整数の数列 Gk(n) で、これは非常に急速に増加する関数となる[1]。
定義[]
非負整数 n を k の冪乗の和として書き、k の指数部をまた同様に k の冪乗の和として書き、という操作を、すべての指数が k 以下となるまで続ける。たとえば、n=100, k=2 として、100 = 26 + 25 + 22 = 222 + 2 + 222 + 1 + 22 と書くことができる。このとき、これを n のk を底とした遺伝的記法と言う。
上記の 100 の遺伝的記法について、底の 2 に 1 を足して 3 として、異なる数字 333 + 3 + 333 + 1 + 33 を作成する。この、より大きい数字を B[2](100) と書き、一般には、B[b](n) は、n の b を底とした遺伝的記法において、底を 1 増やす操作をすることを示すものとする。
ここで、帰納的に数列 G0(n) = n と Gk(n) = B[k + 1](Gk - 1(n)) - 1 を定義することができる。すなわち、 k を増加させるごとに、遺伝的記法の底に 1 を足して、計算された数から 1 を引くのである。これは、次のように計算される。
- G0(100) = 100 = 222 + 2 + 222 + 1 + 22
- G1(100) = B[2](100) - 1 = 333 + 3 + 333 + 1 + 33 - 1 = 228767924549636
- G2(100) = B[3](G1(100)) - 1 = 444 + 4 + 444 + 1 + 2 x 42 + 2 x 1 - 1 = 3.486030062 x 10156
この急速に増加する関数は、グッドスタイン数列として知られている。驚くことに、すべての n に対して、Gk(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のテトレーション配列と同程度の速さで増大することがわかる。この関数はペアノ算術における任意の可証再帰関数[2]よりも速く増大するので、グッドスタインの定理はペアノ算術では証明不可能である。
計算プログラム[]
#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)[3] は \(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\) |
弱いグッドスタイン数列[]
遺伝的記法の代わりに通常の基底表記を用いても、グッドスタインの定理は成り立つとされているが、いくつかの文献では主張と飛躍のある議論のみがなされており証明が書かれていない。
- Weak Goodstein numbers - OEIS A266202: "By Goodstein's theorem we conclude that g_k(n) is a finite sequence."（グッドスタインの定理は弱いグッドスタイン数列の停止性そのものを主張しているわけではないので、2つの数列の停止性に関する含意を示す必要がある。また引用されている出典はこの記事の英語版であり、後述するように証明は記載されていない）
- en:Goodstein_sequence#Weak_Goodstein_function: "If we use the ordinary base representation instead of the hereditary representation, Goodstein's theorem still holds."（停止性の成立が主張されているのみで、証明は記載されていない）
- Weak Goodstein Sequence - projecteuler problem 396: "It can be shown that every weak Goodstein sequence terminates."（停止性の成立が主張されているのみで、証明は記載されていない）
少なくとも１つの文献では停止性の証明とされるものが記載されているが、査読付き出版論文ではないこと、停止ステップ数の定義が上述した定義方法と少し異なることに注意すること。
- p進大好きbot, グッドスタイン数列？ 解説 - yukicoder No.2787
ここで弱いグッドスタイン数列の停止性を仮定した上で、グッドスタイン数列と同じように定義できる数列を弱いグッドスタイン数列\(g(n)\)とする。
グッドスタイン数列と同様、\(g(n)\)もハーディー関数を用いて計算できる。大体急増加関数では\(f_{\omega}(n)\)、矢印表記では\(2 \uparrow^{n-1} n\)と表せる。
| n | g(n)の下限 | g(n)の上限 |
|---|---|---|
| 0 | ||
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | ||
| 8 | ||
| 9 | \(10^{10^{3.5539\times10^{20}}}\) | \(10^{10^{3.5540\times10^{20}}}\) |
| 10 | \((10\uparrow)^4(4.5546\times10^{117})\) | \((10\uparrow)^4(4.5547\times10^{117})\) |
| 11 | \((10\uparrow)^6 (1.9923 \times 10^{619})\) | \((10\uparrow)^6 (1.9924 \times 10^{619})\) |
| 12 | \(10 \uparrow\uparrow 24\) | \(10 \uparrow\uparrow 25\) |
| 13 | \(10 \uparrow\uparrow 65\) | \(10 \uparrow\uparrow 66\) |
| 14 | \(10 \uparrow\uparrow 385\) | \(10 \uparrow\uparrow 386\) |
| 15 | \(10 \uparrow\uparrow 2049\) | \(10 \uparrow\uparrow 2050\) |
| 16 | \((10 \uparrow\uparrow)^{2} (g(8)+5)\) | \((10 \uparrow\uparrow)^{2} (g(8)+6)\) |
| 17 | \((10 \uparrow\uparrow)^{3} (g(9)+7)\) | \((10 \uparrow\uparrow)^{3} (g(9)+8)\) |
| 18 | \((10 \uparrow\uparrow)^{5} (g(10)+9)\) | \((10 \uparrow\uparrow)^{5} (g(10)+10)\) |
| 19 | \((10 \uparrow\uparrow)^{7} (g(11)+11)\) | \((10 \uparrow\uparrow)^{7} (g(11)+12)\) |
| 20 | \(10 \uparrow\uparrow\uparrow 25\) | \(10 \uparrow\uparrow\uparrow 26\) |
| 32 | \(10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow(g(16)+6)\) | \(10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow(g(16)+7)\) |
| 64 | \(10\uparrow\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow\uparrow(g(32)+6)\) | \(10\uparrow\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow\uparrow(g(32)+7)\) |
| \(2^n\) | \(2 \uparrow^{n-1} 5\) | \(2 \uparrow^{n-1} 6\) |
外部リンク[]
- 不見, きりたんの巨大数解説「弱グッドスタイン数列」, ニコニコ動画
出典[]
- ↑ Goodstein Sequence from Wolfram MathWorld
- ↑ Fairtlough, Matt, and Stanley S. Wainer. "Hierarchies of provably recursive functions." Handbook of proof theory 137 (1998): 149-207.
- ↑ Caicedo, A. (2007), "Goodstein's function" (PDF), Revista Colombiana de Matemáticas, 41 (2): 381–391.