A2数列計算表

$f(n)\approx \alpha$ や$f(n)> \alpha$と書かれているときそれは、十分大きな$n$に対して成り立ち、すべての$n$について成り立つわけではないことに注意してください。
$a,b$は任意の正整数です。また$A_k(k\in\mathbb N)$でk番目の要素を表します。
$A2$ 数列内の数字$a$について$ a\underbrace{,...,}_{n個}a$ を$ a^n$ で略記します。
急増加関数$f_\alpha(n)$ はwainer階層を基本列とします。
A(n,$\cdots$,n)はアッカーマン関数です。
\begin{split} (0)[0] &= 0\\ (1)[0] &= (0)^0[0]\\ &= 0\\ (1)[n] &=(0)^n[n]\\ &=2n\\ (1,0)[n] &=(1)[n+1]\\ &=2(n+1)\\ (1,1)[n] &=(\underbrace{1,0,...,1,0}_{n個})[n]\\ &=(\underbrace{1,0,...,1,0}_{n-1個},1)[n+1]\\ &=(\underbrace{1,0,...,1,0}_{n-1個})[2(n+1)]\\ &=(\underbrace{1,0,...,1,0}_{n-2個},1)[2(n+1)+1]\\ &=(\underbrace{1,0,...,1,0}_{n-2個},)[2(2(n+1)+1)]\\ &=(\underbrace{1,0,...,1,0}_{n-3個},1)[2(2(n+1)+1)+1]\\ &=\underbrace{2\uparrow \cdots 2\uparrow }_{n-1個}n+ \sum_{i=0}^{n}2^k\\ &>\underbrace{2\uparrow \cdots \uparrow 2}_{n個}\\ &\approx 2\uparrow\uparrow n\\ (1,1,0)[n] &=(1,1)[n+1]\\ & \approx 2\uparrow\uparrow n\\ (1,1,0,1,1,0)[n] &\approx (1,1,0)[2\uparrow\uparrow n]\\ &\approx 2\uparrow\uparrow (2\uparrow\uparrow n)\\ (1,1,1)[n] &=(\underbrace{1,1,0,...,1,1,0}_{n個})[n]\\ &\approx \underbrace{2\uparrow\uparrow\cdots\uparrow\uparrow 2}_{n個}　= 2\uparrow^3 n\\ (1,1,1,1)[n] &\approx 2\uparrow^4 n\\ (1,1,1,1,1)[n] &\approx 2\uparrow^5 n\\ (1^m)[n] &\approx 2\uparrow^m n\\ (1^n)[n] &\approx 2\uparrow^n n \approx f_{\omega}(n) \approx A(1,0,n)\\ (2)[n] &= (1^n)[n] \approx A(1,0,n)\\ (2,1)[n] \p (\underbrace{2,0,\ddd,2,0}_{n個})[n]\\ \p (\underbrace{2,0,\ddd,2,0}_{n-1個},2)[n+1]\\ \p (\underbrace{2,0,\ddd,2,0}_{n-1個},1^{n})[n]\\ \p (\underbrace{2,0,\ddd,2,0}_{n-2個})[A(1,0,n)]\\ \p (\underbrace{2,0,\ddd,2}_{n-3個},2)[A(1,0,n)]\\ \p (\underbrace{2,0,\ddd,2}_{n-3個})[A(1,0,A(1,0,n))]\\ \p (\underbrace{2,0,\ddd,2}_{n-3個})[A(1,0,A(1,0,A(1,0,n)))]\\ \p \underbrace{A(1,0\cdots ,A(1,0}_{n個},n))\cdots)\\ \p A(1,1,n)\\ (2,1,1)[n] &= (\underbrace{2,1,0,\ddd,2,1,0}_{n個})[n]\\ \p (\underbrace{2,1,0,\ddd,2,1,0}_{n-1個},2,1)[2n]\\ \p (\underbrace{2,1,0,\ddd,2,1,0}_{n-1個})[A(1,1,n)]\\ \p (\underbrace{2,1,0,\ddd,2,1,0}_{n-2個})[A(1,1,A(1,1,n))]\\ \p \underbrace{A(1,1\ddd,A(1,1}_{n個},n))\ddd)\\ \p A(1,2,n)\\ (2,1,1,1)[n] \p (\underbrace{2,1,1,0,\ddd,2,1,1,0}_{n個})[n]\\ \p (\underbrace{2,1,1,0,\ddd,2,1,1,0}_{n-1個},2,1,1)[n+1]\\ \p (\underbrace{2,1,1,0,\ddd,2,1,1,0}_{n-1個})[A(1,2,n)]\\ \p \underbrace{A(1,2,\ddd,A(1,2}_{n-1個},n))\ddd)\\ \p A(1,3,n)\\ (2,1^n)[n] \p A(1,n,n) \approx A(2,0,n) \approx f_{\omega 2}(n)\\ (2,2)[n] &= (\underbrace{2,1^n,\ddd,2,1^n}_{n個})[n]\\ &= (\underbrace{2,1^n,\ddd,2,1^n}_{n-1個})[A(2,0,n))]\\ \p (\underbrace{2,1^n,\ddd,2,1^n}_{n-2個})[A(2,0,A(2,0,n))]\\ \p (\underbrace{2,1^n,\ddd,2,1^n}_{n-3個})[A(2,0,A(2,0,A(2,0,n)))]\\ \p A(3,0,n) \approx f_{\omega 3}(n)\\ (2,2,1)[n] &= (\underbrace{2,2,0^n,\ddd,2,2,0^n}_{n個}) [n]\\ \p (\underbrace{2,2,0^n,\ddd,2,2,0^n}_{n-1個},2,2)[n+1]\\ \p (\underbrace{2,2,0^n,\ddd,2,2,0^n}_{n-1個})[A(3,0,n)]\\ \p (\underbrace{2,2,0^n,\ddd,2,2,0^n}_{n-2個})[A(3,0,A(3,0,n))]\\ \p (\underbrace{2,2,0^n,\ddd,2,2,0^n}_{n-2個})[A(3,0,A(3,0,A(3,0,n)))]\\ \p A(3,1,n)\\ (2,2,1,1)[n] \p (\underbrace{2,2,1,0,\ddd,2,2,1,0}_{n個})[n]\\ \p (\underbrace{2,2,1,0,\ddd,2,2,1,0}_{n個},2,2,1)[n+1]\\ \p (\underbrace{2,2,1,0,\ddd,2,2,1,0}_{n-1個})[A(3,1,n)]\\ \p (\underbrace{2,2,1,0,\ddd,2,2,1,0}_{n-2個})[A(3,1,A(3,1,n))]\\ \p A(3,2,n)\\ (2,2,1^n)[n] &\approx A(3,n,n) \approx A(4,0,n) \approx f_{\omega 4}(n)\\ \p A(4,1,n)\\ (2,2,2,1^n)[n] &\approx A(4,n,n) \approx A(5,0,n) \approx f_{\omega 5}(n) \\ (2^a,1^b)[n] \p A(a+2,b+1,n) \approx f_{\omega\cdot(a+2)+(b+1)}(n)\\ (2^n,1^n)[n] \p A(n,n,n)[n] \approx A(1,0,0,n) \approx f_{\omega^2}(n)\\ (3,1^n)[n] \p A(2,0,0,n) \approx f_{\omega^2 2}\\ (3,2)[n] \p A(2,0,1,n)\\ (3,2,1^n)[n] \p A(2,1,1,n)\\ (3,2^2,1^n)[n] \p A(2,2,1,n)\\ (3,2^a,1^n)[n] \p A(2,a,1,n)\\ (3,2^n,1^n)[n] \p A(3,0,0,n) \approx f_{\omega^2 3}(n)\\ (3^a,2^n,1^n)[n] \p A(a,0,0,n)[n] \approx f_{\omega^2 a}(n)\\ (3^n,2^n,1^n)[n] \p A(n,0,0,n)\approx A(1,0,0,0,n) \approx f_{\omega^3}(n)\\ (\ddd,3^{A_2},2^{A_1},1^{A_0})[n] &\approx f_{\ddd+\omega^2\cdot A_2+\omega\cdot A_1+A_0}(n)\\ (\underbrace{n^n,\cdots,1^n}_{a^nがn個})[n] \p f_{\omega^{\omega}}(n) \end{split}