アッカーマンチェーン定理

著者: ふぃっしゅっしゅ
公開日: 2018年4月14日

アッカーマンチェーン定理は、長さ4以上のコンウェイのチェーン表記を3変数の多変数アッカーマン関数で近似するための定理である。

アッカーマンチェーン定理

x=1, y>1 または x>1, y+z>0 のとき、

A(x,y,z) < C(x+1,y+1,z+2) < A(x,y,z+1)
である。ここで、

なお、このページの変数はすべて自然数（0を含む）である。

例

  1. x=1, y=2, z=1 とすると
    A(1,2,1) < 3→3→3→3 < A(1,2,2)
  2. x=2, y=2, z=1 とすると
    A(2,2,1) < 3→3→3→3→3 < A(2,2,2)
  3. x=3, y=2, z=1 とすると
    A(3,2,1) < 3→3→3→3→3→3 < A(3,2,2)
  4. 3変数アッカーマン関数をチェーン表記で近似
    C(x+1,y+1,z+1) < A(x,y,z) < C(x+1,y+1,z+2)

証明

不等式

A(x,y,z)+1 < C(x+1,y+1,z+2) < A(x,y,z+1) (式1)
が成立する x,y,z の条件を考える。

補題1
A(1,1,z)+1 < C(2,2,z+1) < A(1,1,z+1)-3 (式2)

（証明）

(1) z=0 のときは、

A(1,1,z)+1 = A(1,1,0)+1 = A(1,0,1)+1 = A(0,1,1)+1 = A(1,1)+1 = 4
C(2,2,z+1) = 3→3→1→2 = 3→3 = 27
A(1,1,z+1)-3 = A(1,1,1)-3 = A(1,0,A(1,1,0))-3 = A(1,0,3)-3 = A(3,3)-3 = 61-3 = 58
となり、式2が成立する。ここで、3変数アッカーマン関数の1つ目の変数が0のときは、それを消して2変数として通常のアッカーマン関数と同じように計算できることを使った。

(2) 式2が z=c で成立すると仮定して、z=c+1 で成立することを示す。

アッカーマン関数は x>2 で

A(x,y) = 2↑x-2(y+3)-3 = (2→y+3→x-2)-3
と計算される（証明は巨大数論 p.67）ことから、n>2 で
A(1,0,n) = A(0,n,n) = A(n,n) = (2→n+3→n-2)-3
となる。長さ3のチェーン表記では最右端の数が矢印表記の矢印を重ねる数に相当して演算のレベルを決定づけていることから、A(1,0,n) = (2→n+3→n-2)-3 の大きさについて
(3→3→n-3)+3 < A(1,0,n) < (3→3→n)-1
が成り立つ（1つ目の不等号は n>3 のとき）。 この式に n = A(1,1,z) を代入すると
(3→3→A(1,1,z)-3)+3 < A(1,1,z+1) < (3→3→A(1,1,z))-1 (式3)
となる（1つ目の不等号は z>0 のとき）。ここで
A(1,1,z+1) = A(1,0,A(1,1,z))
を使った。式2に z=c+1 を代入すると
A(1,1,c+1)+1 < C(2,2,c+2) < A(1,1,c+2)-3
となり、この式の1つ目の不等号は
C(2,2,c+2) = 3→3→C(2,2,c+1) > 3→3→A(1,1,c) (仮定より) > A(1,1,c+1)+1 (式3より)
となるため成立し、2つ目の不等号は
C(2,2,c+2) = 3→3→C(2,2,c+1) < 3→3→(A(1,1,c+1)-3) (仮定より) < A(1,1,c+2)-3 (式3より)
となるため成立する。よって (2) が示された。

(1)(2)より補題1が示された。 //

補題2

式1が x=1, y=2 で成立する。

（証明）

示すべき式は

A(1,2,z)+1 < C(2,3,z+2) < A(1,2,z+1) (式4)

(1) z=0 のときは、

A(1,2,z)+1 = A(1,2,0)+1 = A(1,1,1)+1 = 61+1 = 62
C(2,3,2) = 3→3→2→3 = 3→3→27→2 = C(2,2,27)
A(1,2,z+1) = A(1,2,1) = A(1,1,A(1,2,0)) = A(1,1,61)
となり、補題1より C(2,2,27) < A(1,1,61) なので式4が成立する。

(2) z=c で成立すると仮定して、z=c+1 で成立することを示す。

A(1,2,z+1) = A(1,1,A(1,2,z))
であるから、補題1に z=A(1,2,z) を代入して
A(1,2,z+1) < C(2,2,A(1,2,z)+1)-1
補題1に z=A(1,2,z)-1 を代入して
C(2,2,A(1,2,z)) < A(1,2,z+1)-3
すなわち
C(2,2,A(1,2,z)) < A(1,2,z+1) < C(2,2,A(1,2,z)+1)-1 (式5)
となる。式4が z=c で成立するという仮定から
C(2,3,c+3) = C(2,2,C(2,3,c+2)) > C(2,2,A(1,2,c)+1) (仮定より)(注) > A(1,2,c+1)+1 (式5より)
C(2,3,c+3) = C(2,2,C(2,3,c+2)) < C(2,2,A(1,2,c+1)) (仮定より) < A(1,2,c+2) (式5より)
よって式4が z=c+1 で成立する。

(注) ここで C(2,3,c+2) > A(1,2,c)+1 を成立させるため、式1の最初を A(x,y,z) ではなく A(x,y,z)+1 とした。

(1)(2)より補題2が示された。 //

補題3

式1が x=a (a>0), y=b, y+z>0 で成立するときに、x=a, y=b+1 で成立する。

（証明）

(1) x=a, y=b+1, z=0 のときに、式1のそれぞれの不等号が以下のように成立する。

A(a,b+1,0)+1 = A(a,b,1)+1 < C(a+1,b+1,3) (仮定より) < C(a+1,b+1,C(a+1,b+2,1)) = C(a+1,b+2,2)
A(a,b+1,1) = A(a,b,A(a,b,1)) > C(a+1,b+1,A(a,b,1)+1) (仮定より) > C(a+1,b+1,C(a+1,b+1,2)+1) (仮定より) > C(a+1,b+1,C(a,1,3)) = C(a+1,b+1,C(a+1,b+2,1)) = C(a+1,b+2,2)

(2) x=a, y=b+1, z=c で成立すると仮定して、x=a, y=b+1, z=c+1 で成立することを示す。

式1に x=a, y=b, z=A(a,b+1,z)-2 を代入すると

C(a+1,b+1,A(a,b+1,z)) < A(a,b,A(a,b+1,z)-1)
式1に x=a, y=b, z=A(a,b+1,z)-1 を代入すると
A(a,b,A(a,b+1,z)-1)+1 < C(a+1,b+1,A(a,b+1,z)+1)
そして
A(a,b+1,z+1) = A(a,b,A(a,b+1,z))
であるから、以上の3つの式より
C(a+1,b+1,A(a,b+1,z)) < A(a,b+1,z+1) < C(a+1,b+1,A(a,b+1,z)+1)-1 (式6)
となる。式1が x=a, y=b+1, z=c で成立するという仮定より
C(a+1,b+2,c+3) = C(a+1,b+1,C(a+1,b+2,c+2)) > C(a+1,b+1,A(a,b+1,c)+1) (仮定より) > A(a,b+1,c+1)+1 (式6より)
C(a+1,b+2,c+3) = C(a+1,b+1,C(a+1,b+2,c+2) < C(a+1,b+1,A(a+1,b+1,c+1)) (仮定より) < A(a,b+1,c+2) (式6より)
よって式1が x=a, y=b+1, z=c+1 で成立する。

(1)(2)より補題3が示された。 //

補題4

式1が x=1, y>1で成立する。

（証明）

(1) 補題2より式1が x=1, y=2 で成立する。

(2) 補題3より式1が x=1, y=b で成立すれば x=1, y=b+1 で成立する。

(1)(2)より補題4が示された。 //

補題5

式1が x=a, y>1 (a>0) で成立するときに x=a+1, y+z>0 で成立する。

（証明）

(1) x=a+1, y=0, z>0 で式1が成立すること、すなわち

A(a+1,0,z)+1 < C(a+2,1,z+2) < A(a+1,0,z+1) (式7)
を示す。

式1に x=a, y=z+1, z=1 を代入して (z>0 より y>1 なので仮定より式1が成立する)

A(a,z+1,1)+1 < C(a+1,z+2,3) < A(a,z+1,2) (式8)
式7の1つ目の不等号は
C(a+2,1,z+2) = C(a+1,z+2,3) > A(a,z+1,1)+1 (式8より) = A(a,z,A(a,z,1))+1 > A(a,z,z)+1 = A(a+1,0,z)+1
となって成立し、2つ目の不等号は
C(a+2,1,z+2) = C(a+1,z+2,3) < A(a,z+1,2) (式8より) ≤ A(a,z+1,z+1) (z>0 より) = A(a+1,0,z+1)
となって成立する。

(2) (1) と補題3により、式1が x=a+1, y+z>0 で成立する。 すなわち補題5が示された。 //

アッカーマンチェーン定理

x=1, y>1 または x>1, y+z>0 のとき、

A(x,y,z) < C(x+1,y+1,z+2) < A(x,y,z+1)

（証明）

補題4と補題5から、式1が x=1, y>1 または x>1, y+z>0 のときに成立する。

よってこの定理が示された。 //

補足

(補足1) 巨大数論 第2版 p.84 では、A(x,0,z) = A(x-1,z,z) が x+2 変数チェーン表記に相当する大きさの関数となると見積もっている。このページの定理を使えば

C(x,z+1,z+1) < A(x-1,z,z) < C(x,z+1,z+2)
となるため、その見積もりが正しいことが確認できた。

(補足2) 巨大数論 第2版 p.99-100 に、巨大数探索スレッドに2002年に書き込まれたチェーン表記とふぃっしゅ数のS変換との比較の書き込みを引用した。

87 名前：名無しのような物体 ◆W7plq.175s ：02/10/05 15:41

さて、前スレにも書きましたが、3→a-2→b < 2→a→b < 3→a-1→b であることが確認できました。
一応帰納法で証明しましたが･･･読みたいですか？

さらに、これを用いて
B(x,y) =(2→(y+3)→(x-2))-3
　　　　≒3→(y+1～2)→(x-2)
C(x,y) ≒3→3→(y+1～2)→(x+1)
D(x,y) ≒3→3→3→(y+1～2)→(x+1)
まで計算できました。どうやらＳ変換1回で 3→ がひとつ延長されるようです。
これでいよいよふぃっしゅ数が(近似的に)求められる･･･のか？

これを多変数アッカーマン関数に直したものがこのページの定理である。巨大数探索スレッドには詳しい計算過程は書き込まれていなかったため検証した。

(補足3) 巨大数クイズ Q23 で出題された。正解者2名、正答率22%。

ふぃっしゅっしゅ