Fandom

巨大数研究 Wiki

コメント0

アッカーマン関数の簡潔な表記

Hex347 2016年2月27日 User blog:Hex347

この記事は執筆中です。

アッカーマン関数は理解しづらいなと思っていました。しかし、考えを巡らせていたところ、アッカーマン関数を簡潔な表記で表す方法を見つけましたのでここにメモします。

アッカーマン関数

アッカーマン関数の展開

アッカーマン関数は非負の整数に対して次のようにして定義されます。

\[ A(x,y)= \begin{cases} y+1 & \text{if}\ x=0, \\ A(x-1,1) & \text{if}\ y=0 \\ A(x-1,A(x,y-1)) & \text{otherwise}. \end{cases} \]

これを計算するときの過程の一例を見てください。

\[ \begin{array}{cclclcl} A(2,2) &=& A(1,A(2,1))\\ &=& A(1,A(1,A(2,0)))&&\\ &=& A(1,A(1,A(1,1)))\\ &=& A(1,A(1,A(0,A(1,0))))\\ &=& A(1,A(1,A(0,A(0,1))))\\ &=& A(1,A(1,A(0,2)))\\&=& A(1, A(1, 3))\\ &=& A(1, A(0, A(1, 2)))\\ &=& A(1, A(0, A(0, A(1, 1))))\\ &=& A(1, A(0, A(0, A(0, A(1, 0)))))\\ &=& A(1, A(0, A(0, A(0, A(0, 1)))))\\ &=& A(1, A(0, A(0, A(0, 2))))\\ &=& A(1, A(0, A(0, 3)))\\ &=& A(1, A(0, 4))\\ &=& A(1, 5)\\ &=& A(0, A(1, 4))\\ &=& A(0, A(0, A(1, 3)))\\ &=& A(0, A(0, A(0, A(1, 2))))\\ &=& A(0, A(0, A(0, A(0, A(1, 1)))))\\ &=& A(0, A(0, A(0, A(0, A(0, A(1, 0))))))\\ &=& A(0, A(0, A(0, A(0, A(0, A(0, 1))))))\\ &=& A(0, A(0, A(0, A(0, A(0, 2)))))\\ &=& A(0, A(0, A(0, A(0, 3))))\\ &=& A(0, A(0, A(0, 4)))\\ &=& A(0, A(0, 5))\\ &=& A(0, 6)\\ &=& 7 \end{array} \]

非常に長い計算過程ですが、ここにあるパターンを見つけることが出来ます。全ての関数が\( \text{A}(n,*) \)という形になっています。するとこのように表記することが出来ます。

  • \( \text{A}(m,n) = m : n \) として、関数のネストは \( \text{A}(m,\text{A}(n,o)) = m : (n : o) = m : n : o \) とする。

こうするとアッカーマン関数の計算過程が簡潔に表記できます。

表記により分かる規則性

たとえば、計算過程はこのようになります。

\[ \begin{array}{cclclcl} 2:2 &=& 1:2:1 \\ &=& 1:1:2:0 \\ &=& 1:1:1:1 \\ &=& 1:1:0:1:0 \\ &=& 1:1:0:0:1 \\ &=& 1:1:0:2 \\ &=& 1:1:3 \\ &=& 1:0:1:2 \\ &=& 1:0:0:1:1 \\ &=& 1:0:0:0:1:0 \\ &=& 1:0:0:0:0:1 \\ &=& 1:0:0:0:2 \\ &=& 1:0:0:3 \\ &=& 1:0:4 \\ &=& 1:5 \\ &=& 0:1:4 \\ &=& 0:0:1:3 \\ &=& 0:0:0:1:2 \\ &=& 0:0:0:0:1:1 \\ &=& 0:0:0:0:0:1:0 \\ &=& 0:0:0:0:0:0:1 \\ &=& 0:0:0:0:0:2 \\ &=& 0:0:0:0:3 \\ &=& 0:0:0:4 \\ &=& 0:0:5 \\ &=& 0:6 \\ &=& 7 \end{array} \]

さて、ここでアッカーマン関数の規則性がよくわかります。第一に、いちばん深い所、左の方の所に1の壁が出来ている点です。これは\(\text{A}(x,y)\)においてまずはyを計算しないとxを減らすことが出来ないということを示しています。次に、左の壁が一つ減るごとに右側の値が0の積み重なりになり、最終的にyが大きく増加する点です。この\(2:2\)の計算ではまだ見れない規則性があります。次は\(4:0\)を計算します。

\[ \begin{array}{cclclcl} 4:0 &=& 3:1 \\ &=& 2:3:0 \\ &=& 2:2:1 \\ &=& 2:1:2:0 \\ &=& 2:1:1:1 \\ &=& 2:1:0:1:0 \\ &=& 2:1:0:0:1 \\ &=& 2:1:0:2 \\ &=& 2:1:3 \\ &=& 2:0:1:2 \\ &=& 2:0:0:1:1 \\ &=& 2:0:0:0:1:0 \\ &=& 2:0:0:0:0:1 \\ &=& 2:0:0:0:2 \\ &=& 2:0:0:3 \\ &=& 2:0:4 \\ &=& 2:5 \\ &=& 1:2:4 \\ &=& 1:1:2:3 \\ &=& 1:1:1:2:2 \\ &=& 1:1:1:1:2:1 \\ &=& 1:1:1:1:1:2:0 \\ &=& 1:1:1:1:1:1:1 \\ &=& 1:1:1:1:1:0:1:0 \\ &=& 1:1:1:1:1:0:0:1 \end{array} \]

このくらいにしておきます。さて、2の壁がなくなったとき、大量の1が出来ました。1の壁は積み重なった0の壁を作り、2の壁は積み重なった1の壁を作り、nの壁は積み重なったn-1の壁を作るというのが、もう一つの規則性です。

このリストのような表記法で計算するというのは、「アッカーマン関数」「スタック」と検索すれば出てくる手法です。

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

Fandomでも見てみる

おまかせWikia