アッカーマン関数は大きい (O(アッカーマン関数(n,n))とO(n^n^...^n)ってどっちが大きいの？)

O(アッカーマン関数) は どのくらいでかいか？

「アッカーマン関数は非常に巨大になる」という話をどこかで聞いたことがあると思う
また、下のようなことをしたこともあるかもしれない

• Python的なものでアッカーマン関数を実装して計算時間が長すぎて Ctrl+C
• オーバーフローしてみる
• 計算結果の桁数が何桁かを数えてみてドヒャーって言ってみる
• 計算の途中式を表示してみる

ではアッカーマン関数は我々の良く知る関数と比べどのくらい大きいのだろうか？

例えば、下の関数だとどの辺に位置するのか？ちょっと考えてみてほしい

O(n), O(2n), O(3n),...,O(n*n)
O(n^1), O(n^2), O(n^3),...,O(2^n), O(3^n), O(4^n),...,O(n^n)
O(n^n), O(n^n^n), O(n^n^n^n),...,O(2^2^...^2) , O(3^3^...^3), O(4^4^...^4),...,O(n^...^n), #(nがn個)
...

・・・
・・
・

で、結論を言うとアッカーマン関数は上で挙げたどの関数よりも大きくなる
そういった話をする

アッカーマン関数の定義と特性

アッカーマン関数は以下の定義を持つ再帰関数である

Ack(0, y) = y + 1 ;
Ack(x, 0) = Ack(x-1, 1) ;
Ack(x, y) = Ack(x-1, Ack(x, y-1))

1. ちゃんと計算できる(特定の値を入れるとバグって無限ループに陥ったりとかがない)
2. 再帰関数である
3. 繰り返す処理を繰り返す関数である

3の「 繰り返す処理を繰り返す関数」であるというのは、
アッカーマン関数をゴリゴリ変形していくと下の形になるのだが

Ack(x,y) = g^x(a=>a+1)(y)
# ただし
f^c(x) = xにfをc回適応することを指すとする. 
g(f)(a)= f^(a+1)(1) 

gはfをa回繰り返す関数で、アッカーマン関数はそれをx回繰り返している。
つまりざっくりいうとアッカーマン関数は繰り返す処理を繰り返す関数である

アッカーマン関数とハイパー演算子

ハイパー演算子とは

ハイパー演算子というのは、足し算をn=1、掛算をn=2、べき乗をn=3...のように+*^...を一般化した概念である

hyper(x,1,y) = x + y
hyper(x,2,y) = x * y = (x+(x+(x+...))) = hyper(x,1,hyper(x,1,hyper(x,1,...)))
hyper(x,3,y) = x ^ y = (x*(x*(x*...))) = hyper(x,2,hyper(x,2,hyper(x,2,...)))
hyper(x,4,y) = (x^(x^(x^...))) = hyper(x,3,hyper(x,3,hyper(x,3,...)))
hyper(x,5,y) =  hyper(x,4,hyper(x,4,hyper(x,4,...)))
...
hyper(x,n,y) =  hyper(x,n-1,hyper(x,n-1,hyper(x,n-1,...hyper(x,n-1,x)...)))
## hyper(x,0,y)やhyper(x,n,0) については説明が増えるので省略

rubyで書くとこんな感じ

def hyper(x,n,y)
   n==1? x+y : 
   n==2? x*y :
   n==3? x**y : 
   ([x]*y).reduce{|r,l| hyper(l,n-1,r)}  # なんでrubyにはfoldr相当の関数がないんだ
end

上のとおり、ハイパー演算子は reduceで処理を繰り返す処理であり、そして再帰処理なのでさらにそれを繰り返す
つまりざっくりいうとハイパー演算子というのは「繰り返す処理を繰り返す」関数である

アッカーマン関数のハイパー演算子への変換

読者は勘がいいのでお気づきだと思うが、アッカーマン関数はハイパー演算子に変換でき、
大体 Ack(x, y) ≒ hyper(2,x,y) になる

# アッカーマン関数はハイパー演算子に変換できる
Ack(x,y) = hyper(2, x, y + 3) - 3

# x=1について成り立つことの証明
Ack(1, y) 
= Ack(0, Ack(1, y-1)) # どんどん展開していく
= Ack(0, Ack(0, ... Ack(1, 0)... )) 
= Ack(0, Ack(0, ... Ack(0, 1)... )) 
= 1 + (1 + (...(1 + (1)) ...))  # Ack(0, a) -> (1 + a) に変換
= y + 2
= hyper(2, 1, y + 3) - 3

# 本当はx==3まで証明しなきゃいけないんだけどめんどいから省略

# Ack(a, y) = hyper(2, a, y + 3) - 3 が成り立つとして、
# Ack(a+1, y) = hyper(2, a + 1, y + 3) - 3 が成り立つことを示す

Ack(a+1, y)
= Ack(a,Ack(a,Ack(a,...Ack(a+1,0)...)))  # どんどん展開
= Ack(a,Ack(a,Ack(a,...Ack(a,1)...)))
= hyper(2,a,hyper(2,a,hyper(2,a,...hyper(2,a,1+3)-3...+3)-3+3)-3+3)-3 # Ack(a, y) -> hyper(2, a, y + 3) - 3
= hyper(2,a,hyper(2,a,hyper(2,a,...hyper(2,a,4)...)))-3  # `y+3`の+3と`)-3`の-3がいい感じに打ち消しあう
= hyper(2,a,hyper(2,a,hyper(2,a,...hyper(2,a,hyper(2,a,2))...)))-3  # 任意のcで `4 = hyper(2,c,2)` より
= hyper(2,a+1,y+3)-3


# 「任意のcで `4 = hyper(2,c,2)`」について
hyper(a,c,2) = hyper(a,c-1,a) # なので
hyper(2,c,2) = hyper(2,c-1,2) = hyper(2,c-2,2) = ... 2^2 = 2*2 = 2+2 = 4

#よって
Ack(x,y) = hyper(2, x, y + 3) - 3

O(アッカーマン関数(n,n))とO(n^n^...^n)ってどっちが大きいの？

元の式	ハイパー演算子表記
O(Ack(x,y))	O(hyper(2,x,y))
O(n^n^...^n)	O(hyper(n,4,n))

O(n+n) < O(n*n) < O(n^n) であることからわかるように、ハイパー演算子というのは第二引数が1つふえると急激に大きくなる
その第二引数の部分を無限に増大させたものについて考えるのが O(hyper(c,n,c)) であり、
これは第二引数が定数である O(hyper(x,c,y)) より大きい

したがってO(アッカーマン関数(n,n)) と O(n^n^...^n) は、アッカーマン関数のほうが大きい

アッカーマン関数は大きい

O(n^n^...^n)がO(hyper(n,4,n))であることは話したが、この関数だって小さくない。
というか、多分我々が人生で見る関数のなかではトップクラスにデカイ

「桁数」表現できる数字が 高々 O(10^n)
「桁数の桁数」で表現できる数字が高々 O(10^10^n)
「桁数の桁数の桁数」で表現できる数字が高々 O(10^10^10^n)
"桁数"+"の桁数"*n で表現できる数字が O(10^10^...^n)
そしてO(n^n^...^n)　はそれよりおおきい

hyper(n,5,n) は当然それらより大きく、hyper(n,6,n) はそれよりもはるかに大きく、hyper(n,c,n) (c>6)はめっちゃ大きい

そしてアッカーマン関数はそれらの数よりも常にはるかに大きい。
アッカーマン関数はそういう大きさである

補1: アッカーマン関数より大きい関数

まず単純に Ack(x+c,c) とかAck(x*c,c) とかAck(x^c,c) とか、
そしてそれらよりめちゃくちゃデカイ Ack(Ack(x,c),c) とかそして Ack(Ack(Ack(x,c),c),c) とか

アッカーマン関数を6,70回ほど繰り返して作る数 Ack(Ack(...Ack(x,c)...,c),c) が(かの有名な)グラハム数に大体なる
アッカーマン関数を"アッカーマン関数を繰り返して作った数"回繰り返してもいいし、それを繰り返してもいい
アッカーマン関数が「繰り返す処理を繰り返す処理」であることから「繰り返す処理を繰り返す寄りを繰り返す処理」を想像してもいいし、もっと繰り返してもいい

補2: 他のアッカーマン関数より小さい関数

ここまでの話で(アッカーマン関数より大きい関数作ろうとしない限り)大体小さいんじゃね？って気持ちになったと思うが、
「原始再帰関数」と呼ばれる関数はアッカーマン関数より厳密に小さい

また、大体の関数は原始再帰関数に属するらしいので、
大体の関数はアッカーマン関数より小さい小さい

原始再帰関数は以下のような関数である

• リテラル、四則演算、すでに原始再帰関数であることがわかってる関数 で構成された関数
• 以下を満たす関数f
  • f(X,0)が原始再帰関数であることが証明できる
  • f(X,c)が原始再帰関数であると仮定したとき、f(X,c+1)が原始再帰関数だといえる

プログラミング的には（スタックを使う再帰やmalloc等を使わずに）for文だけで書ける処理と大体一致する

そういった関数はアッカーマン関数より小さい

原始再帰関数の数学的定義とアッカーマン関数より小さいことの証明

原始再帰関数の数学的定義

以下の関数は原始再帰関数である
- Zero() = 0
- Succ(x) = x+1
- Projection<n>(x...) = # 引数のn番目を返す
- 以下を満たす関数f
  - h,g0,g1,...は原始再帰関数とする
  - f(x...) = h(g0(x...),g1(x...),...)
- 以下を満たす関数f
  - g,hは原始再帰関数とする
  - f(0,x...) = g(x...)
  - f(n,x...) = h(n-1,f(n-1,x...),x...)

原始再帰関数がアッカーマン関数より小さいことの証明

定義の5つの関数がアッカーマン関数より小さいことを示せばよい。つまり
f(x...) <= Ack(c,sum(x...)) なるcが存在すればよい

# 1-3
Zero()  <  Ack(0,x)
Succ(x) == Ack(0,x)
Projection<n>(x...) <  Ack(0, sum(x...))

# 4
f(x...)
= h(g0(x...),g1(x...),...) 
<= Ack(ch, sum(g0(x...),g1(x...),...)) 
<= Ack(ch, Ack(cg,sum(x...)))  # sum(g0(x...),g1(x...),...) < n*g<k>(x...) < Ack(cg,sum(x...))
< Ack(max(ch,cg), Ack(max(ch,cg)+1, sum(x...)))
= Ack(max(ch,cg)+1,sum(x...)+1)
= Ack(max(ch,cg)+1, Ack(1,sum(x...)-1)) # Ack(1,x) = x+2より
<= Ack(max(ch,cg)+1, Ack(max(ch,cg)+2, sum(x...)-1))
= Ack(max(ch,cg)+2, sum(x...))
= Ack(c, max(x...))
## よって4で定義できる関数は ch,cgが存在するとき、cが存在する

# 5 
g(x...) <= Ack(cg,sum(x...)) 
h(x...) <= Ack(ch,sum(x...))
なるcg,chが存在するとする

f(n,x...) < Ack(cf, sum(x...)) (cf>=max(ch+2,)) 
なるcfがそんざいするとして
f(0,x...)
= g(x...)
<= Ack(cg,sum(0,x...))
<= Ack(c,sum(0,x...))

f(n+1,x...) 
= h(n,f(n,x...),x...)
<= Ack(ch, sum(n,f(n,x...),x...))
<= Ack(ch, sum(n,Ack(cf,sum(n,x...)),x...))
<= Ack(ch, 2*Ack(cf,sum(n,x...)))
<= Ack(ch+1, Ack(cf,sum(n,x...)))
<= Ack(cf-1, Ack(cf,sum(n,x...))) 
= Ack(cf, sum(n,x...)+1)
= Ack(cf, sum(n+1,x...))
## よって帰納法より f(n,x...) <= Ack(cf,sum(x...)) なるcfが存在する

## よって5で定義できる関数は cg,chが存在するとき、f(n,x...) <= Ack(c,sum(x)...)) になるcは存在する

# 1-5 より、原始再帰関数は「アッカーマン関数より小さい関数」と「使用する関数がアッカーマン関数より小さいなら自身もアッカーマン関数より小さい関数」しかないので
# 原始再帰関数はアッカーマン関数より小さい