巨大数研究 Wiki
登録
Advertisement
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

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

2nest-hydra2

\([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


出典[]

関連項目[]

Aeton: おこじょ数N成長階層
mrna: 段階配列表記降下段階配列表記多変数段階配列表記横ネスト段階配列表記
Kanrokoti: くまくまψ関数亜原始ψ関数ハイパー原始ψ関数TSS-ψ関数
クロちゃん: クロちゃん数第一第ニ第三第四
じぇいそん: ふにゃふにゃぜぇたかんすう\(\zeta\)関数
たろう: 多変数アッカーマン関数2重リストアッカーマン関数多重リストアッカーマン関数
Nayuta Ito: フラン数第一形態第二形態第四形態改三)・N原始東方巨大数4の規則の境界を突いた巨大数
バシク: 原始数列数大数列数ペア数列数バシク行列システム
長谷川由紀路: 紅魔館のメイドナンバー恋符マスタースパーク数みくみく順序数
108Hassium: E2:B-01-HsL-階差数列類E3:B-02-Hs
公太郎: 弱亜ペア数列肉ヒドラ数列弱ハイパーペア数列
p進大好きbot: 超限急増加関数表記拡張ブーフホルツのψ関数に伴う順序数表記四関数三関数巨大数庭園数
ふぃっしゅ: ふぃっしゅ数バージョン1バージョン2バージョン3バージョン4バージョン5バージョン6バージョン7)・ マシモ関数マシモスケールTR関数I0関数
ゆきと: 亜原始数列ハイパー原始数列Y数列
本: 巨大数論寿司虚空編
大会: 東方巨大数幻想巨大数即席巨大数式神巨大数お料理巨大数
掲示板: 巨大数探索スレッド名もなき巨大数研究
外部リンク: 日本語の巨大数関連サイト



Advertisement