Graviness Blog

算数・数学・科学・電脳・雑記・アホの順の密度で記事が構成されます。
<< November 2018 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 >> ブログランキング・にほんブログ村へ
 
RECOMMEND
ビッグバン宇宙論 (上)
ビッグバン宇宙論 (上) (JUGEMレビュー »)
サイモン・シン, 青木 薫
RECENT COMMENT
  • 豊臣秀吉と曾呂利新左衛門から学ぶ数列の和
    優乃 (07/12)
  • 【誰か解いて】漸化式 a_(n+1) = f(n) * a_n ^ g(n) + h(n) の一般項
    優乃 (02/18)
  • 【誰か解いて】漸化式 a_(n+1) = f(n) * a_n ^ g(n) + h(n) の一般項
    S.S.+ (02/16)
  • 豊臣秀吉と曾呂利新左衛門から学ぶ数列の和
    坂井昭 (03/19)
  • d/dx(x↑↑n): 高さが定数のテトレーションの微分 - 数学的帰納法を用いる方法
    (09/30)
  • 全ての三角形は二等辺三角形
    優乃 (09/28)
  • 全ての三角形は二等辺三角形
    亀レス (09/28)
  • 全ての三角形は二等辺三角形
    優乃 (09/24)
  • 全ての三角形は二等辺三角形
    亀レス (09/23)
  • 【未解決】新しい演算子を創る
    $_ (09/10)
RECENT TRACKBACK
MOBILE
qrcode
PROFILE
無料ブログ作成サービス JUGEM
 
アッカーマン関数(模索編)
アッカーマン関数は、非負整数に対し、次のように定義される関数です。
・・・

2回の記事に分けて、多重矢印演算子(タワー表記)を使えば、次のように表現できることを証明します。
・・・
以降では、証明までの道のりを記しますが、証明する気なんてさらさらなかったので、しばらく“なんか”しようと模索してます。ご勘弁をw


アッカーマン関数は、引数が増加するにつれて、再帰的な計算量と関数の返値が爆発的に増加する関数です。少し実際の計算例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

あっ、無理・・・^^;  Ack(1,21) を求めるところで諦めました ^^; 実際、Ack(4,1) は、65533 となるようです。さらに、1だけ大きい Ack(4,2) は、極端に大きくなって、265533-3 となるようです。

上記をジーッと見てると、Ack(1,k) は、k+2 、Ack(2,k) は、2k+3と予想できます。なんとか、証明できないものでしょうか。



(ここからしばらく、高校生なら分かるアッカーマン関数の定式化作業が続きます。)



簡単そうなから行きます。のとき、アッカーマン関数の定義より
・・・
ここで、漸化式の一般項をとおけば、上記は
・・・
となり、これは、公差を1とする等差数列なので解けて
・・・
ここで、なので
・・・
これは、のときも成り立つ。


次に、です。のとき、アッカーマン関数の定義と、より
・・・
ここで、漸化式の一般項をとおけば、上記は
・・・
となり、これは、公差を2とする等差数列なので解けて
・・・
ここで、なので
・・・
これは、のときも成り立つ。


次に、です。のとき、アッカーマン関数の定義と、より
・・・
ここで、漸化式の一般項をとおけば、上記は
・・・
となり、変形すると
・・・
ここで、とおけば、となり、これは、公比を2とする等比数列の形なので、解けて
・・・
ゆえに
・・・
ここで、なので
・・・
ゆえに
・・・
これは、のときも成り立つ。



第一引数が増えるにつれ、足し算、掛け算、べき算と、演算のレベルが増大していくのが分かります。



次に、です。のとき、アッカーマン関数の定義とより
・・・
ここで、漸化式の一般項をとおけば、上記は
・・・
となり、-3を左辺に移項し、とおくと
・・・
ここで
・・・
以下、べき乗演算子をとし、タワー表記をもちいる。
・・・
と続き、結局
・・・
が得られる。ゆえに
・・・
これは、となり、のときも成り立つ。



もう一個くらい行ってみます。



次に、です。のとき、アッカーマン関数の定義とより
・・・
ここで、漸化式の一般項をとおけば、上記は
・・・
となり、-3を左辺に移項し、と置くと
・・・
ここで
・・・
さらに
・・・
と続き、結局
・・・
が得られる。ゆえに
・・・
これは
・・・
となり、のときも成り立つ。



求めてみると結局、3重矢印演算子、4重矢印演算子、、、n重矢印演算子としていく操作に見えます。次回の記事で、以下の証明に挑戦します。
・・・


少し話がそれますが、巨大数論(PDF) は、グラハム数より本質的に大きい巨大数(大きくできる関数)を創る試みですが、私には雰囲気しか分かりませんでしたが、面白かったです。g(2) で既にグラハム数を超えてるとかw あと、数の大体の大きさを知るのに対数関数を使ったりしますが、それの巨大数バージョン Hardy関数も興味深かったです。



関連記事)
・アッカーマン関数(模索編)
アッカーマン関数(証明編)

参考)
アッカーマン関数@wikipedia
クヌースの矢印表記@wikipedia

JUGEMテーマ:学問・学校
コメント
コメントする









 
トラックバック
この記事のトラックバックURL
http://blog.graviness.com/trackback/949241
 

(C) 2018 ブログ JUGEM Some Rights Reserved.