FANDOM


2重リストアッカーマン関数のページで、ぼちぼちと計算をしているけど、

\[A([n, 1], [n]) \approx f_{\omega^\omega}(n)\]

これがようやく分かった。次に、リストの中を多変数化したときは、これも多変数アッカーマンと同じような関係になっていることは想像出来るのだけど、なかなか具体的な計算として納得出来ない。

それにしても、よくこんな式を考えついたものだ。

バード氏も多重リストをやっているので、比較したらどうなるか。

\[A([1,2,3,4],[5,6],[7]) \approx f_{\omega^{(\omega^2+\omega\times2+3)\times 4}+\omega^{5-1} \times 6}(7) \]

こんな感じか?indexの大きい順番というのは、順序数の計算では大きい順序数から先に足さないといけないから。

式は複雑なんだけど、きちんと理解さえできれば、順序数との対応がきっちりとできるのはいいよなぁ。

つまり、この順序数のヒドラツリーを書いてみれば、2重リストアッカーマン漸化式の構造が見えるということか。

とりあえず定義式を貼っておく。

\begin{eqnarray} A(Y_1, [X, 0], Y_2) & = & A(Y_1, Y_2) \\ A(Y_1, [Z, X], Y_2) & = & A(Y_1, [X], Y_2) \\ \\ A([a]) & = & a+1 \\ A(Y, [1, b+1]) & = & A(Y, [1, b], [1]) \\ A(Y, [1, b+1], [a+1]) & = & A( Y, [1, b], [A(Y, [1, b+1], [a])] ) \\ A(Y, [X, c+1, b+1], [a]) & = & A(Y, [X, c+1, b], [X, c, a], [a]) ... X \neq Z or c \neq 0 \\ A(Y, [X, c+1, 0, Z, b+1], [a]) & = & A(Y, [X, c+1, 0, Z, b], [X, c, a, Z, a], [a]) \end{eqnarray}

そして、評価式はこれ

\[A([..., b_3, b_2, b_1, b_0, a], [n]) \approx f_{\omega^{(... + \omega^3・b_3 + \omega^2・b_2 + \omega・b_1 + b_0)・a}}(n)\]

リストが3つ以上あるときは、リストに対応する順序数を全部足せばいいのかな?

まずはこれ \[A(Y, [1, b+1], [a+1]) = A( Y, [1, b], [A(Y, [1, b+1], [a])] ) \]

左辺は、Yに対応する順序数を\(\alpha\)として、 \[f_{\alpha + \omega^{b+1}}(a+1)\] 右辺は、 \[f_{\alpha + \omega^{b}} (f_{\alpha + \omega^{b+1}}(a))\] ううん、これはイコールなのか?ちょっと面倒なので後回し。

続いてこれ

\[A(Y, [X, c+1, b+1], [a]) = A(Y, [X, c+1, b], [X, c, a], [a]) ... X \neq Z or c \neq 0 \]

左辺は、Xに対応する順序数を\(\beta\)として、 \[f_{\alpha + \omega^{(\beta + c+1) \times (b+1)}}(a)\] 右辺は、 \[f_{\alpha + \omega^{(\beta + c+1) \times b} + \omega^{(\beta + c) \times a}}(a)\] ううむ、これもよく分からないな。

続いて、最後の式。この式は、多変数との対応で使ってなかったので、重要だろう。

\[A(Y, [X, c+1, 0, Z, b+1], [a]) = A(Y, [X, c+1, 0, Z, b], [X, c, a, Z, a], [a])\]

左辺は \[f_{\alpha + \omega^{(\beta + \omega^n (c+1)) \times (b+1)}}(a)\]

右辺は \[f_{\alpha + \omega^{(\beta + \omega^n (c+1)) \times b}+\omega^{(\beta + \omega^n c + \omega^{n-1} \times a) \times a}}(a)\]

順序数の足し算で計算すると、なんともならないなぁ。掛け算なのかな。それならば、指数の部分は足し算できるのだけど。

ヒドラツリーを描いて、アップしてみた。図を間違えたので新しいファイルに差し替えたのだけど、サムネール画像はすぐには更新されないのか、古い画像が表示されている。

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


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

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

FANDOMでも見てみる

おまかせWiki