アッカーマン関数（模索編）
アッカーマン関数
は、非負整数
と
に対し、次のように定義される関数です。
２回の記事に分けて、多重矢印演算子（タワー表記）を使えば、次のように表現できることを証明します。
以降では、証明までの道のりを記しますが、証明する気なんてさらさらなかったので、しばらく“なんか”しようと模索してます。ご勘弁をｗ
は、非負整数とに対し、次のように定義される関数です。 | ・・・ |
２回の記事に分けて、多重矢印演算子（タワー表記）を使えば、次のように表現できることを証明します。
 | ・・・ |
アッカーマン関数は、引数が増加するにつれて、再帰的な計算量と関数の返値が爆発的に増加する関数です。少し実際の計算例Ack(4,1) を手計算で書いてみます。
A(4,1)=A(3,A(4,0))=A(3,13)=
A(4,0)=A(3,1)=13
A(3,1)=A(2,A(3,0))=A(2,5)=13
A(3,0)=A(2,1)=5
A(2,1)=A(1,A(2,0))=A(1,3)=5
A(2,0)=A(1,1)=3
A(1,1)=A(0,A(1,0))=A(0,2)=3
A(1,0)=A(0,1)=2
A(1,3)=A(0,A(1,2))=A(0,4)=5
A(1,2)=A(0,A(1,1))=A(0,3)=4
A(2,5)=A(1,A(2,4))=A(1,11)=13
A(2,4)=A(1,A(2,3))=A(1,9)=11
A(2,3)=A(1,A(2,2))=A(1,7)=9
A(2,2)=A(1,A(2,1))=A(1,5)=7
A(1,5)=A(0,A(1,4))=A(0,6)=7
A(1,4)=A(0,A(1,3))=A(0,5)=6
A(1,7)=A(0,A(1,6))=A(0,8)=9
A(1,6)=A(0,A(1,5))=A(0,7)=8
A(1,9)=A(0,A(1,8))=A(0,10)=11
A(1,8)=A(0,A(1,7))=A(0,9)=10
A(1,11)=A(0,A(1,10))=A(0,12)=13
A(1,10)=A(0,A(1,9))=A(0,11)=12
A(3,13)=A(2,A(3,12))=
A(3,12)=A(2,A(3,11))=
A(3,11)=A(2,A(3,10))=
A(3,10)=A(2,A(3,9))=
A(3,9)=A(2,A(3,8))=
A(3,8)=A(2,A(3,7))=
A(3,7)=A(2,A(3,6))=
A(3,6)=A(2,A(3,5))=
A(3,5)=A(2,A(3,4))=
A(3,4)=A(2,A(3,3))=
A(3,3)=A(2,A(3,2))=
A(3,2)=A(2,A(3,1))=A(2,13)=
A(2,13)=A(1,A(2,12))=
A(2,12)=A(1,A(2,11))=
A(2,11)=A(1,A(2,10))=
A(2,10)=A(1,A(2,9))=A(1,21)=
A(2,9)=A(1,A(2,8))=A(1,19)=21
A(2,8)=A(1,A(2,7))=A(1,17)=19
A(2,7)=A(1,A(2,6))=A(1,15)=17
A(2,6)=A(1,A(2,5))=A(1,13)=15
A(1,13)=A(0,A(1,12))=A(0,14)=15
A(1,12)=A(0,A(1,11))=A(0,13)=14
A(1,15)=A(0,A(1,14))=A(0,16)=17
A(1,14)=A(0,A(1,13))=A(0,15)=16
A(1,17)=A(0,A(1,16))=A(0,18)=19
A(1,16)=A(0,A(1,15))=A(0,17)=18
A(1,19)=A(0,A(1,18))=A(0,20)=21
A(1,18)=A(0,A(1,17))=A(0,19)=20
A(4,0)=A(3,1)=13
A(3,1)=A(2,A(3,0))=A(2,5)=13
A(3,0)=A(2,1)=5
A(2,1)=A(1,A(2,0))=A(1,3)=5
A(2,0)=A(1,1)=3
A(1,1)=A(0,A(1,0))=A(0,2)=3
A(1,0)=A(0,1)=2
A(1,3)=A(0,A(1,2))=A(0,4)=5
A(1,2)=A(0,A(1,1))=A(0,3)=4
A(2,5)=A(1,A(2,4))=A(1,11)=13
A(2,4)=A(1,A(2,3))=A(1,9)=11
A(2,3)=A(1,A(2,2))=A(1,7)=9
A(2,2)=A(1,A(2,1))=A(1,5)=7
A(1,5)=A(0,A(1,4))=A(0,6)=7
A(1,4)=A(0,A(1,3))=A(0,5)=6
A(1,7)=A(0,A(1,6))=A(0,8)=9
A(1,6)=A(0,A(1,5))=A(0,7)=8
A(1,9)=A(0,A(1,8))=A(0,10)=11
A(1,8)=A(0,A(1,7))=A(0,9)=10
A(1,11)=A(0,A(1,10))=A(0,12)=13
A(1,10)=A(0,A(1,9))=A(0,11)=12
A(3,13)=A(2,A(3,12))=
A(3,12)=A(2,A(3,11))=
A(3,11)=A(2,A(3,10))=
A(3,10)=A(2,A(3,9))=
A(3,9)=A(2,A(3,8))=
A(3,8)=A(2,A(3,7))=
A(3,7)=A(2,A(3,6))=
A(3,6)=A(2,A(3,5))=
A(3,5)=A(2,A(3,4))=
A(3,4)=A(2,A(3,3))=
A(3,3)=A(2,A(3,2))=
A(3,2)=A(2,A(3,1))=A(2,13)=
A(2,13)=A(1,A(2,12))=
A(2,12)=A(1,A(2,11))=
A(2,11)=A(1,A(2,10))=
A(2,10)=A(1,A(2,9))=A(1,21)=
A(2,9)=A(1,A(2,8))=A(1,19)=21
A(2,8)=A(1,A(2,7))=A(1,17)=19
A(2,7)=A(1,A(2,6))=A(1,15)=17
A(2,6)=A(1,A(2,5))=A(1,13)=15
A(1,13)=A(0,A(1,12))=A(0,14)=15
A(1,12)=A(0,A(1,11))=A(0,13)=14
A(1,15)=A(0,A(1,14))=A(0,16)=17
A(1,14)=A(0,A(1,13))=A(0,15)=16
A(1,17)=A(0,A(1,16))=A(0,18)=19
A(1,16)=A(0,A(1,15))=A(0,17)=18
A(1,19)=A(0,A(1,18))=A(0,20)=21
A(1,18)=A(0,A(1,17))=A(0,19)=20
あっ、無理・・・^^; Ack(1,21) を求めるところで諦めました ^^; 実際、Ack(4,1) は、65533 となるようです。さらに、1だけ大きい Ack(4,2) は、極端に大きくなって、265533-3 となるようです。
上記をジーッと見てると、Ack(1,k) は、k+2 、Ack(2,k) は、2k+3と予想できます。なんとか、証明できないものでしょうか。
（ここからしばらく、高校生なら分かるアッカーマン関数の定式化作業が続きます。）
簡単そうな
から行きます。
のとき、アッカーマン関数の定義より | ・・・ |
とおけば、上記は
 | ・・・ |
 | ・・・ |
なので
 | ・・・ |
のときも成り立つ。
次に、
です。のとき、アッカーマン関数の定義と、
より | ・・・ |
とおけば、上記は
 | ・・・ |
 | ・・・ |
なので
 | ・・・ |
のときも成り立つ。
次に、
です。のとき、アッカーマン関数の定義と、
より | ・・・ |
とおけば、上記は
 | ・・・ |
 | ・・・ |
とおけば、
となり、これは、公比を2とする等比数列の形なので、解けて
 | ・・・ |
 | ・・・ |
なので
 | ・・・ |
 | ・・・ |
のときも成り立つ。第一引数が増えるにつれ、足し算、掛け算、べき算と、演算のレベルが増大していくのが分かります。
次に、
です。のとき、アッカーマン関数の定義とより | ・・・ |
とおけば、上記は
 | ・・・ |
とおくと
 | ・・・ |
 | ・・・ |
とし、タワー表記をもちいる。
 | ・・・ |
 | ・・・ |
 | ・・・ |
となり、のときも成り立つ。もう一個くらい行ってみます。
次に、
です。のとき、アッカーマン関数の定義と
より | ・・・ |
とおけば、上記は
 | ・・・ |
と置くと
 | ・・・ |
 | ・・・ |
 | ・・・ |
 | ・・・ |
 | ・・・ |
 | ・・・ |
のときも成り立つ。求めてみると結局、3重矢印演算子、4重矢印演算子、、、n重矢印演算子としていく操作に見えます。次回の記事で、以下の証明に挑戦します。
 | ・・・ |
少し話がそれますが、巨大数論(PDF) は、グラハム数より本質的に大きい巨大数（大きくできる関数）を創る試みですが、私には雰囲気しか分かりませんでしたが、面白かったです。g(2) で既にグラハム数を超えてるとかｗ あと、数の大体の大きさを知るのに対数関数を使ったりしますが、それの巨大数バージョン Hardy関数も興味深かったです。
関連記事)
・アッカーマン関数（模索編）
・アッカーマン関数（証明編）
参考)
・アッカーマン関数＠wikipedia
・クヌースの矢印表記＠wikipedia
JUGEMテーマ：学問・学校
