Googology Wiki
Register
Googology Wiki
(→‎Calculation: Comparison with chained arrow notation)
Line 48: Line 48:
 
Following relationship was calculated.<ref>[http://gyafun.jp/ln/ackchain.html Ackermann chain theorem]</ref>
 
Following relationship was calculated.<ref>[http://gyafun.jp/ln/ackchain.html Ackermann chain theorem]</ref>
   
\[A(x,y,z) < \underbrace{3 \rightarrow3 \rightarrow \cdots \rightarrow 3}_{x+1 3s} \rightarrow z+2 \rightarrow y+1 < A(x,y,z+1)\]
+
\[A(x,y,z) < \underbrace{3 \rightarrow3 \rightarrow \cdots \rightarrow 3}_{x+1 reps of 3s} \rightarrow z+2 \rightarrow y+1 < A(x,y,z+1)\]
   
 
Therefore function A(x,y,z) has recursive level corresponding to x+3 variables of Conway's chained arrow notation, and A(1,0,1,2) exceeds Conway's [[chained arrow notation]] with Graham's numbers length.
 
Therefore function A(x,y,z) has recursive level corresponding to x+3 variables of Conway's chained arrow notation, and A(1,0,1,2) exceeds Conway's [[chained arrow notation]] with Graham's numbers length.

Revision as of 06:42, 14 April 2018

Taro's multivariable Ackermann function
Based onsuccessor function
Growth rate\(f_{\omega^\omega}(n)\)

Taro's multivariable Ackermann function \(A(x_1,x_2, …, x_n)\) is a recursive function invented by a Japanese googologist Taro (2007) and described by Fish (2013) [1]. It is similar to Ackermann function with 2 variables, and with more than 3 variables grows at similar rate with Array notation, despite its simple definition.

Definition

  • X : vector of integers larger than or equal to 0, with the length larger than or equal to 0 (ex., [3, 1, 0, 0])
  • Y : vector of 0 with the length larger than or equal to 0 (ex., [0, 0, 0, 0, 0])
  • a, b : integer larger than or equal to 0

\begin{eqnarray*} A(Y, 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, Y, a ) & = & A(X, b, a, Y, a) \end{eqnarray*}

Calculation

Secret of the fast rate of growing of this function is in the 4th equation. In order to reduce the "b" variable by 1, it diagonizes the right variable from 0 to a. It is enough to make strong recursion. If we count the variables from right to left, 2nd variable recurses the 1st variable (primitive recursion in Ackermann function), 3rd variable recurses the second variable, where recursion of primitive recursion makes double recursion, 4th variable recurses the 3rd variable. As the 'n'th variable recurses the 'n-1'th variable, level of recursion steadily goes up.

Example calculation is shown to compare this with Graham's number with help of Conway's chained arrow notation. With 2 variable, it is similar to standard Ackermann function and can be compared as

\begin{eqnarray*} A(x,y) & \approx & 3 \rightarrow y \rightarrow x-2 \\ \end{eqnarray*}

With 3 variables,

\begin{eqnarray*} A(1,1,0) & = & A(1,0,1) = A(0,1,1) = A(1,1) = 3 \\ A(1,1,1) & = & A(1,0,A(1,1,0)) = A(1,0,3) = A(3,3) = 61 \\ A(1,1,2) & = & A(1,0,61) = A(61,61) > 3 \rightarrow 3 \rightarrow 2 \rightarrow 2 \\ A(1,1,3) & \approx & A(1,0,3 \rightarrow 3 \rightarrow 2 \rightarrow 2) \approx 3 \rightarrow 3 \rightarrow 3 \rightarrow 2 \\ A(1,1,4) & \approx & A(1,0,3 \rightarrow 3 \rightarrow 2 \rightarrow 3) \approx 3 \rightarrow 3 \rightarrow 4 \rightarrow 2 \\ A(1,1,x) & \approx & 3 \rightarrow 3 \rightarrow x \rightarrow 2 \\ A(1,1,65) & \approx & 3 \rightarrow 3 \rightarrow 65 \rightarrow 2 > G \\ A(1,2,0) & = & A(1,1,1) = 61 \\ A(1,2,1) & = & A(1,1,61) > 3 \rightarrow 3 \rightarrow 61 \rightarrow 2 \\ A(1,2,2) & \approx & A(1,1,3 \rightarrow 3 \rightarrow 61 \rightarrow 2) > 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 61 \rightarrow 2) \rightarrow 2 > A(1,1,65) \end{eqnarray*}

And therefore A(1,2,2) > A(1,1,65) > Graham's number.

Following relationship was calculated.[2]

\[A(x,y,z) < \underbrace{3 \rightarrow3 \rightarrow \cdots \rightarrow 3}_{x+1 reps of 3s} \rightarrow z+2 \rightarrow y+1 < A(x,y,z+1)\]

Therefore function A(x,y,z) has recursive level corresponding to x+3 variables of Conway's chained arrow notation, and A(1,0,1,2) exceeds Conway's chained arrow notation with Graham's numbers length.

\begin{eqnarray*} A(1,0,1,0) & = & A(1,0,0,1) = A(1,0,1) = A(1,1) = 3 \\ A(1,0,1,1) & = & A(1,0,0,A(1,0,1,0)) \\ & = & A(1,0,0,3) = A(3,0,3) = A(2,3,3) \\ A(1,0,1,2) & = & A(1,0,0,A(1,0,1,1)) \\ & = & A(1,0,0,A(2,3,3)) \\ & = & A(A(2,3,3),0,A(2,3,3)) \approx \underbrace{3 \rightarrow 3 \rightarrow 3 ... 3 \rightarrow 3 \rightarrow 3}_{A(2,3,3)} \end{eqnarray*}

The growth rate of this function was compared with fast-growing hierarchy as follows.

\begin{eqnarray*} A(n, n) & \approx & f_{\omega}(n) \\ A(1, 0, n) & \approx & f_{\omega}(n) \\ A(a, 0, n) & \approx & f_{\omega・a}(n) \\ A(n, 0, n) & \approx & f_{\omega^2}(n) \\ A(1, 0, 0, n) & \approx & f_{\omega^2}(n) \\ A(a, 0, 0, n) & \approx & f_{\omega^2・a}(n) \\ A(n, 0, 0, n) & \approx & f_{\omega^3}(n) \\ A(1, 0, 0, 0, n) & \approx & f_{\omega^3}(n) \\ A(a, 0, 0, 0, n) & \approx & f_{\omega^3・a}(n) \\ A(n, 0, 0, 0, n) & \approx & f_{\omega^4}(n) \\ A(..., a3, a2, a1, a0, n) & \approx & f_{... + \omega^3・a3 + \omega^2・a2 + \omega・a1 + a0}(n) \\ A(\underbrace{1,1,...,1}_n) & \approx & f_{\omega^\omega}(n) \\ \end{eqnarray*}

Approximations in other notations

\(A(..., d, c, b, a, n)\) is approximated as follows.

Notation Approximation
Bowers' Exploding Array Function \(\lbrace n,2,a+1,b+1,c+1,d+1,... \rbrace\)
Fast-growing hierarchy \(f_{... \omega^3 d + \omega^2 c + \omega b + a}(n)\)
Hardy hierarchy \(H_{\omega^{... \omega^3 d + \omega^2 c + \omega b + a} }(n)\)

Sources

See also