Fandom

巨大数研究 Wiki

2重リストアッカーマン関数

548このwikiの
ページ数
新しいページをつくる
コメント0 シェアする
2重リストアッカーマン関数
基本関数 後者関数
急増加関数 \(f_{\omega^{\omega^\omega}}(n)\)

2重リストアッカーマン関数 は、2007年にたろうが考案し[1]、ふぃっしゅっしゅ(2013)[2]に紹介された。

多変数アッカーマン関数を2重リストに拡張する。多変数アッカーマンのn個目の引数がaであることを、[n, a] と表現するようにし、[ ] の中を多変数化することで拡張する。 \(f_{\omega^{\omega^\omega}}(n)\) 位の増大度の関数となる。さらに、同様の拡張を繰り返すことで、多重リストアッカーマン関数が定義できるとしたが、具体的な定義は与えられていない。

  • X: 0個以上の0以上の整数
  • Y, Y_1, Y_2 : 0個以上の0以上の整数リスト
  • Z : 0個以上の0
  • a, b, c : 0以上の整数

N : 十分大きな整数に対し、

\begin{eqnarray*} \mathrm{index} [..., b_3, b_2, b_1, b_0, a_0] = ... + N^3・b_3 + N^2・b_2 + N・b_1 + b_0 \end{eqnarray*}

とし、 \(A( )\) の中のリストは index の大きい順に表記する。 また、index が同じとなるリストは \(A( )\) 内に複数含まないとする。

\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}

近似 編集

この関数の大きさは、急増加関数および多変数アッカーマン関数と比較して、次のように評価された。その具体的な計算は、このページで検証中。

\begin{eqnarray*} A([n, 1], [n]) & \approx & f_{\omega^\omega}(n) \\ A([1, 0, 1], [n]) & \approx & f_{\omega^\omega}(n) \\ A([a, 0, 1], [n]) & \approx & f_{\omega^{\omega・a}}(n) \\ A([n, 0, 1], [n]) & \approx & f_{\omega^{\omega^2}}(n) \\ A([1, 0, 0, 1], [n]) & \approx & f_{\omega^{\omega^2}}(n) \\ A([a, 0, 0, 1], [n]) & \approx & f_{\omega^{\omega^2・a}}(n) \\ A([n, 0, 0, 1], [n]) & \approx & f_{\omega^{\omega^3}}(n) \\ A([1, 0, 0, 0, 1], [n]) & \approx & f_{\omega^{\omega^3}}(n) \\ A([1, 0, 0, 0, 0, 1], [n]) & \approx & f_{\omega^{\omega^4}}(n) \\ A([1, 0, 0, 0, 0, 0, 1], [n]) & \approx & f_{\omega^{\omega^5}}(n) \\ \\ A(..., [3, a_3], [2, a_2], [1, a_1], [0, a_0]) & = & A(a_3, a_2, a_1, a_0) \\ 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) \\ A([\underbrace{1,1,...,1}_n], [n]) & \approx & f_{\omega^{\omega^\omega}}(n) \end{eqnarray*}

計算 編集

多変数アッカーマンの漸化式 \begin{eqnarray*} A(Z, a) & = & a+1 \\ A(X, b+1, 0) & = & A(X, b, 1) \\ A(X, b+1, a+1) & = & A( X, b, A(X, b+1, a) ) \\ A(X, b+1, 0, Z, a ) & = & A(X, b, a, Z, a) \end{eqnarray*} に対して、 \[A(a_3, a_2, a_1, a_0) = A(..., [3, a_3], [2, a_2], [1, a_1], [0, a_0])\] とすると、\([X,0]\) の項は取り除かれることを考慮して、 \begin{eqnarray*} 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, [c+1,b+1], [a] ) & = & A(Y, [c+1,b+1], [c,a] [a]) \end{eqnarray*} となる。この式は、2重リストアッカーマンの定義式と一致するため、 \[A(..., [3, a_3], [2, a_2], [1, a_1], [0, a_0]) = A(a_3, a_2, a_1, a_0)\] の式が成り立つ。したがって、

\[A([n, 1], [n]) = A(1,\underbrace{0,0,...,0}_{n-1},n) \approx f_{\omega^\omega}(n) \]

である。

次に、2重リストの中が3変数以上の時の計算を見る。ここでは、ヒドラゲームを使ってその計算を見る。

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

この式において、左辺が順序数 \(\beta + \omega^{(\alpha + c+1) \times (b+1)}(a)\) に対応するとして、(ここで、\(\alpha\)、\(\beta\)はそれぞれ X と Y に対応する順序数)、左辺の \(A(Y, [X, c+1, b+1], [a])\) に対応するヒドラツリーを書くと

2nest-hydra1.png

この図の「Cut here !」の首を切ると、新しく \([X, c, 1]\) のヒドラが a 個、つまり \([X, c, a]\) が生えてきて、

2nest-hydra2.png

\([X, c+1, 1]\) は a 本足されて a+1 本なので、厳密にはこのように \([X, c, a+1]\) となるところ、aが十分に大きければ +1 は無視出来るとして a にしたのではないかと考えられる。

プログラム編集

Ruby(とegison gem) による2重リストアッカーマン関数の展開の様子は以下。

require 'rubygems'
require 'egison'

include Egison

def ack_next(arr)
	return arr if(arr.class !=Array)
	res=[[[arr]]]
	t=res
	
	while(t.class==Array && t.last.class==Array && t.last.last.class==Array && t.last.last.last.class==Array) do
		t=t.last
	end
	
	target=t.last.dup
	
	match(target) do
		with(_[*_y1,_[*_x,0],*_y2]) do
			print "Pattern 1\n"
			t[-1]=y1+y2
		end
		
		with(_[*_y1,_[0,*_x],*_y2]) do
			print "Pattern 2\n"
			t[-1]=y1+[x]+y2
		end
		
		with(_[_[_a]]) do
			print "Pattern 3\n"
			t[-1]=[a+1]
		end
		
		with(_[*_y4,_[1,_b]]) do
			print "Pattern 4\n"
			t[-1]=y4+[[1,b-1],[1]]
		end
		
		with(_[*_y5,_[1,_b],_[_a]]) do
			print "Pattern 5\n"
			t[-1]=y5+[[1,b-1], y5+[[1,b],[a-1]]]
		end
		
		with(_[*_y6,_[*_x,_c,0,*_z,_b],_[_a]]) do
			print "Pattern 6\n"
			t[-1]=y6+[x+[c,0]+z+[b-1],x+[c-1,a]+z+[a],[a]]
		end
		
		with(_[*_y7,_[*_x,_c,_b],_[_a]]) do
			print "Pattern 7\n"
			t[-1]=y7+[x+[c,b-1],x+[c-1,a],[a]]
		end
	
		with(_) do
			print "ERROR\n"
			return []
		end
	end
	return res[0][0][0]
end

x=[[1,1,1],[3]]
p x
while(x.class==Array && x.last.class==Array) do
	x=ack_next(x)
	p x
	gets
end


出典編集

  1. 巨大数探索スレッド7@2ch数学板でアップされた文書 (たろう, 2007年10月17日)
  2. ふぃっしゅっしゅ (2013) 巨大数論

関連項目 編集



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


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

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

Fandomでも見てみる

おまかせWiki