Googology Wiki
Advertisement
Googology Wiki
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 an extension of the Ackermann function invented by a Japanese googologist Taro in 2007 and described by Fish in 2013[1].

It is similar to Ackermann function with 2 variables, and with more than 3 variables grows at similar rate as 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*}

In other words:

  • If all but/and the last variable are zeros,the function value is the successor of the last variable. (1st case)
  • If the second to last variable is a non-zero: (2nd or 3rd case)
    • If the last variable is zero: (2nd case)
      • Replace the last variable to 1. 
      • Reduce the second to last variable in 1.
    • Else: (3rd case)
      • Replace the last variable with value of the function, but with its last variable reduced by 1.
      • Reduce the second to last variable in 1.
  • Else (the second to last entry is a end of a Y vector (which will be named Z)): (4th case)
    • Replace the first variable of Z with the last variable.
    • Reduce the last variable before Z by 1.

Calculation

The fast growth rate of this function is primarily because of the 4th case of the definition. In order to reduce the "b" variable by 1, it diagonizes the right variable from 0 to a. This is enough to make some 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 nth variable recurses the (n-1)th variable, the "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 variables, 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.

The following relationship was calculated:[2]

For \(x=1, y>1\) or \(x>1, y+z>0\)

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

Therefore function A(x,y,z) has a 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 number variables.

\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
BEAF and Bird's array notation \(\lbrace n,2,a+1,b+1,c+1,d+1,... \rbrace\)
X-Sequence Hyper-Exponential Notation \(n\{... + X^3 d + X^2 c + Xb + a\}n\)
Strong array notation \(s(n,n,a+1,b+1,c+1,d+1,...)\)
Username5243's Array Notation \(n[a,b,c,d,...]n\)
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)\)
Slow-growing hierarchy ???

Sources

See also

Original numbers, functions, notations, and notions

By Aeton: Okojo numbers · N-growing hierarchy
By 新井 (Arai): Arai's psi function
By バシク (BashicuHyudora): Primitive sequence number · Pair sequence number · Bashicu matrix system 1/2/3/4 original idea
By ふぃっしゅ (Fish): Fish numbers (Fish number 1 · Fish number 2 · Fish number 3 · Fish number 4 · Fish number 5 · Fish number 6 · Fish number 7 · S map · SS map · s(n) map · m(n) map · m(m,n) map) · Bashicu matrix system 1/2/3/4 formalisation · TR function (I0 function)
By Gaoji: Weak Buchholz's function
By じぇいそん (Jason): Irrational arrow notation · δOCF · δφ · ε function
By 甘露東風 (Kanrokoti): KumaKuma ψ function
By koteitan: Bashicu matrix system 2.3
By mrna: 段階配列表記 · 降下段階配列表記 · 多変数段階配列表記 · SSAN · S-σ
By Naruyoko Naruyo: Y sequence formalisation · ω-Y sequence formalisation
By Nayuta Ito: N primitive · Flan numbers (Flan number 1 · Flan number 2 · Flan number 3 · Flan number 4 version 3 · Flan number 5 version 3) · Large Number Lying on the Boundary of the Rule of Touhou Large Number 4
By Okkuu: Extended Weak Buchholz's function
By p進大好きbot: Ordinal notation associated to Extended Weak Buchholz's function · Ordinal notation associated to Extended Buchholz's function · Naruyoko is the great · Large Number Garden Number
By たろう (Taro): Taro's multivariable Ackermann function
By ゆきと (Yukito): Hyper primitive sequence system · Y sequence original idea · YY sequence · Y function · ω-Y sequence original idea


Methodology

By バシク (BashicuHyudora): Bashicu matrix system as a notation template
By じぇいそん (Jason): Shifting definition
By mrna: Side nesting
By Nayuta Ito and ゆきと (Yukito): Difference sequence system


Implementation of existing works into programs

Proofs, translation maps for analysis schema, and other mathematical contributions

By ふぃっしゅ (Fish): Computing last 10000 digits of mega · Translation map for primitive sequence system and Cantor normal form
By Kihara: Proof of an estimation of TREE sequence · Proof of the incomparability of Busy Beaver function and FGH associated to Kleene's \(\mathcal{O}\)
By koteitan: Translation map for primitive sequence system and Cantor normal form
By Naruyoko Naruyo: Translation map for Extended Weak Buchholz's function and Extended Buchholz's function
By Nayuta Ito: Comparison of Steinhaus-Moser Notation and Ampersand Notation
By p進大好きbot: Proof of the termination of Hyper primitive sequence system · Proof of the termination of Pair sequence number · Proof of the termination of segements of TR function in the base theory under the assumption of the \(\Sigma_1\)-soundness and the pointwise well-definedness of \(\textrm{TR}(T,n)\) for the case where \(T\) is the formalisation of the base theory


Entertainments

By 小林銅蟲 (Kobayashi Doom): Sushi Kokuu Hen
By koteitan: Dancing video of a Gijinka of Fukashigi · Dancing video of a Gijinka of 久界 · Storyteller's theotre video reading Large Number Garden Number aloud


See also: Template:Googology in Asia
Advertisement