Editing Ackermann function (section)

==Computation==
The recursive definition of the Ackermann function can naturally be transposed to a [[Rewriting#Term rewriting systems|term rewriting system (TRS)]].

===TRS, based on 2-ary function===
The definition of the '''<u>2-ary</u>''' Ackermann function leads to the obvious reduction rules{{sfn|Grossman|Zeitman|1988}}{{sfn|Paulson|2021}}

<math display="block"> 
\begin{array}{lll}
\text{(r1)} & A(0,n)       & \rightarrow & S(n) \\
\text{(r2)} & A(S(m),0)    & \rightarrow & A(m,S(0)) \\
\text{(r3)} & A(S(m),S(n)) & \rightarrow & A(m,A(S(m),n))
\end{array}
</math>

'''Example'''

Compute <math>A(1,2) \rightarrow_{*} 4</math>

The reduction sequence is <ref group="n" name="letop5">In each ''step'' the underlined ''redex'' is rewritten.</ref>

{| style="border-collapse:collapse"
|style="text-align:left; border-right: solid thin black; padding-right: 0.5em"|[[Reduction strategy#Term rewriting|Leftmost-outermost (one-step) strategy]]:{{space|12}}
|style="text-align:left; padding-left: 0.5em"|[[Reduction strategy#Term rewriting|Leftmost-innermost (one-step) strategy]]:
|-
|style="border-right: solid thin black; padding-right: 0.5em"|<math>\underline{{A(S(0),S(S(0)))}}</math>
|style="padding-left: 0.5em"|<math>\underline{{A(S(0),S(S(0)))}}</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{r3} \underline{{A(0,A(S(0),S(0))}})</math>
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r3} A(0,\underline{{A(S(0),S(0))}})</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{r1}  S(\underline{{A(S(0),S(0))}})</math>
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r3}  A(0,A(0,\underline{{A(S(0),0)}}))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{r3}	S(\underline{{A(0,A(S0,0))}})</math>
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r2}	A(0,A(0,\underline{{A(0,S(0))}}))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{r1}	S(S(\underline{{A(S(0),0)}}))</math>
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r1}	A(0,\underline{{A(0,S(S(0)))}})</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{r2}	S(S(\underline{{A(0,S(0))}}))</math>
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r1}	\underline{{A(0,S(S(S(0))))}}</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{r1}	S(S(S(S(0))))</math>
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r1}	S(S(S(S(0))))</math>
|-
|}

To compute <math>\operatorname{A}(m, n)</math> one can use a [[Stack (abstract data type)|stack]], which initially contains the elements <math>\langle m,n \rangle</math>.

Then repeatedly the two top elements are replaced according to the rules<ref group="n" name="letop2">here: leftmost-innermost strategy!</ref>

<math display="block">
\begin{array}{lllllllll}
\text{(r1)} & 0     &,& n     & \rightarrow & (n+1) \\
\text{(r2)} & (m+1) &,& 0     & \rightarrow & m &,& 1 \\
\text{(r3)} & (m+1) &,& (n+1) & \rightarrow & m &,& (m+1) &,& n
\end{array}
</math>

Schematically, starting from <math>\langle m,n \rangle</math>:

 '''WHILE''' stackLength <> 1
 {
    '''POP''' 2 elements;
    '''PUSH''' 1 or 2 or 3 elements, applying the rules r1, r2, r3
 }

The [[pseudocode]] is published in {{harvtxt|Grossman|Zeitman|1988}}.

For example, on input <math>\langle 2,1 \rangle</math>,
{| style="border-collapse:collapse"
|style="text-align:left; border-right: solid thin black; padding-right: 0.5em"|the stack configurations{{space|4}}
|style="text-align:left; padding-left: 0.5em"|reflect the reduction<ref group="n" name="letop1">For better readability<br/>S(0) is notated as 1,<br />S(S(0)) is notated as 2,<br />S(S(S(0))) is notated as 3,<br/>etc...</ref>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|<math>\underline{2,1}</math> 
|style="padding-left: 0.5em"|<math>\underline{A(2,1)}</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow 1,\underline{2,0}</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r1} A(1,\underline{A(2,0)})</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow 1,\underline{1,1}</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r2} A(1,\underline{A(1,1)})</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow 1,0,\underline{1,0}</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r3} A(1,A(0,\underline{A(1,0)}))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow 1,0,\underline{0,1}</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r2} A(1,A(0,\underline{A(0,1)}))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow 1,\underline{0,2}</math> 		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r1} A(1,\underline{A(0,2)})</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow \underline{1,3}</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r1} \underline{A(1,3)}</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow 0,\underline{1,2}</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r3} A(0,\underline{A(1,2)})</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow 0,0,\underline{1,1}</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r3} A(0,A(0,\underline{A(1,1)}))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow 0,0,0,\underline{1,0}</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r3} A(0,A(0,A(0,\underline{A(1,0)})))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow 0,0,0,\underline{0,1}</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r2} A(0,A(0,A(0,\underline{A(0,1)})))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow 0,0,\underline{0,2}</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r1} A(0,A(0,\underline{A(0,2)}))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow 0,\underline{0,3}</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r1} A(0,\underline{A(0,3)})</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow \underline{0,4}</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r1} \underline{A(0,4)}</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow 5</math>											
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r1} 5</math>
|}

'''Remarks'''
*The leftmost-innermost strategy is implemented in 225 computer languages on [[Rosetta Code]].
*For all <math>m,n</math> the computation of <math>A(m,n)</math> takes no more than <math>(A(m,n) + 1)^m</math> steps.{{sfn|Cohen|1987|p=56|loc=Proposition 3.16 (see in proof)}}
*{{harvtxt|Grossman|Zeitman|1988}} pointed out that in the computation of <math>\operatorname{A}(m,n)</math> the maximum length of the stack is <math>\operatorname{A}(m,n)</math>, as long as <math>m>0</math>.<p> Their own algorithm, inherently iterative, computes <math>\operatorname{A}(m,n)</math> within <math>\mathcal{O}(m \operatorname{A}(m,n))</math> time and within <math>\mathcal{O}(m)</math> space.</p>

===TRS, based on iterated 1-ary function===
The definition of the iterated <u>'''1-ary'''</u> Ackermann functions leads to different reduction rules

<math display="block"> 
\begin{array}{lll}
\text{(r4)} & A(S(0),0,n)    & \rightarrow & S(n) \\
\text{(r5)} & A(S(0),S(m),n) & \rightarrow & A(S(n),m,S(0)) \\
\text{(r6)} & A(S(S(x)),m,n) & \rightarrow & A(S(0),m,A(S(x),m,n))
\end{array}
</math>

As function composition is associative, instead of rule r6 one can define

<math display="block">
\begin{array}{lll}
\text{(r7)} & A(S(S(x)),m,n) & \rightarrow & A(S(x),m,A(S(0),m,n))
\end{array}
</math>

Like in the previous section the computation of <math>\operatorname{A}^1_m(n)</math> can be implemented with a stack.

Initially the stack contains the three elements <math>\langle 1,m,n \rangle</math>.

Then repeatedly the three top elements are replaced according to the rules<ref group="n" name="letop2"/>

<math display="block">
\begin{array}{lllllllll}
\text{(r4)} & 1   &, 0   &, n & \rightarrow & (n+1) \\
\text{(r5)} & 1   &, (m+1) &, n & \rightarrow & (n+1) &, m &, 1 \\
\text{(r6)} & (x+2) &, m   &, n & \rightarrow & 1 &, m &, (x+1) &, m &, n \\
\end{array}
</math>

Schematically, starting from <math>\langle 1, m,n \rangle</math>:
 '''WHILE''' stackLength <> 1
 {
    '''POP''' 3 elements;
    '''PUSH''' 1 or 3 or 5 elements, applying the rules r4, r5, r6;
 }

'''Example'''

On input <math>\langle 1,2,1 \rangle</math> the successive stack configurations are

<math display="block">\begin{align}
& \underline{1,2,1}
  \rightarrow_{r5} \underline{2,1,1} 
  \rightarrow_{r6} 1,1,\underline{1,1,1}
  \rightarrow_{r5} 1,1,\underline{2,0,1}
  \rightarrow_{r6} 1,1,1,0,\underline{1,0,1} \\
& \rightarrow_{r4} 1,1,\underline{1,0,2}
  \rightarrow_{r4} \underline{1,1,3}
  \rightarrow_{r5} \underline{4,0,1}
  \rightarrow_{r6} 1,0,\underline{3,0,1}
  \rightarrow_{r6} 1,0,1,0,\underline{2,0,1} \\
& \rightarrow_{r6} 1,0,1,0,1,0,\underline{1,0,1}
  \rightarrow_{r4} 1,0,1,0,\underline{1,0,2}
  \rightarrow_{r4} 1,0,\underline{1,0,3}
  \rightarrow_{r4} \underline{1,0,4}
  \rightarrow_{r4} 5
\end{align}</math>

The corresponding equalities are

<math display="block">\begin{align}
& A_2(1)
  = A^2_1(1)
  = A_1(A_1(1))
  = A_1(A^2_0(1))
  = A_1(A_0(A_0(1))) \\
& = A_1(A_0(2))
  = A_1(3)
  = A^4_0(1)
  = A_0(A^3_0(1))
  = A_0(A_0(A^2_0(1))) \\
& = A_0(A_0(A_0(A_0(1))))
  = A_0(A_0(A_0(2)))
  = A_0(A_0(3))
  = A_0(4)
  = 5
\end{align}</math>

When reduction rule r7 is used instead of rule r6, the replacements in the stack will follow

<math display="block">\begin{array}{lllllllll}
\text{(r7)} & (x+2) &, m   &, n & \rightarrow & (x+1) &, m &, 1 &, m &, n
\end{array}</math>

The successive stack configurations will then be

<math display="block">\begin{align}
& \underline{1,2,1}
  \rightarrow_{r5} \underline{2,1,1} 
  \rightarrow_{r7} 1,1,\underline{1,1,1}
  \rightarrow_{r5} 1,1,\underline{2,0,1}
  \rightarrow_{r7} 1,1,1,0,\underline{1,0,1} \\
& \rightarrow_{r4} 1,1,\underline{1,0,2}
  \rightarrow_{r4} \underline{1,1,3}
  \rightarrow_{r5} \underline{4,0,1}
  \rightarrow_{r7} 3,0,\underline{1,0,1}
  \rightarrow_{r4} \underline{3,0,2} \\
& \rightarrow_{r7} 2,0,\underline{1,0,2}
  \rightarrow_{r4} \underline{2,0,3}
  \rightarrow_{r7} 1,0,\underline{1,0,3}
  \rightarrow_{r4} \underline{1,0,4}
  \rightarrow_{r4} 5
\end{align}</math>

The corresponding equalities are 

<math display="block">\begin{align}
& A_2(1)
  = A^2_1(1)
  = A_1(A_1(1))
  = A_1(A^2_0(1))
  = A_1(A_0(A_0(1))) \\
& = A_1(A_0(2)) = A_1(3) 
  = A^4_0(1)
  = A^3_0(A_0(1))
  = A^3_0(2) \\
& = A^2_0(A_0(2))
  = A^2_0(3)
  = A_0(A_0(3))
  = A_0(4) = 5
\end{align}</math>

'''Remarks'''
*On any given input the TRSs presented so far converge in the same number of steps. They also use the same reduction rules (in this comparison the rules r1, r2, r3 are considered "the same as" the rules r4, r5, r6/r7 respectively). For example, the reduction of <math>A(2,1)</math> converges in 14 steps: 6 × r1, 3 × r2, 5 × r3. The reduction of <math>A_2(1)</math> converges in the same 14 steps: 6 × r4, 3 × r5, 5 × r6/r7. The TRSs differ in the order in which the reduction rules are applied.
*When <math>A_{i}(n)</math> is computed following the rules {r4, r5, r6}, the maximum length of the stack stays below <math>2 \times A(i,n)</math>. When reduction rule r7 is used instead of rule r6, the maximum length of the stack is only <math>2(i+2)</math>. The length of the stack reflects the recursion depth. As the reduction according to the rules {r4, r5, r7} involves a smaller maximum depth of recursion,<ref group="n" name="letop6">The maximum depth of recursion refers to the number of levels of activation of a procedure which exist during the deepest call of the procedure. {{harvtxt|Cornelius|Kirby|1975}}</ref> this computation is more efficient in that respect.

===TRS, based on hyperoperators===
As {{harvtxt|Sundblad|1971}} &mdash; or {{harvtxt|Porto|Matos|1980}} &mdash; showed explicitly, the Ackermann function can be expressed in terms of the [[hyperoperation]] sequence:

<math display="block">A(m,n) = \begin{cases}
 n+1 & m=0 \\
 2[m](n+3) - 3 & m>0 \\
\end{cases}</math>

or, after removal of the constant 2 from the parameter list, in terms of Buck's function
  
<math>A(m,n) = \begin{cases}
 n+1 & m=0 \\
 F(m,n+3) - 3 & m>0 \\
\end{cases}</math>

Buck's function <math>\operatorname{F}(m,n) = 2[m]n</math>,{{sfn|Buck|1963}} a variant of Ackermann function by itself, can be computed with the following reduction rules:

<math display="block"> 
\begin{array}{lll}
\text{(b1)} & F(S(0),0,n)          & \rightarrow & S(n) \\
\text{(b2)} & F(S(0),S(0),0)       & \rightarrow & S(S(0)) \\
\text{(b3)} & F(S(0),S(S(0)),0)    & \rightarrow & 0 \\
\text{(b4)} & F(S(0),S(S(S(m))),0) & \rightarrow & S(0) \\
\text{(b5)} & F(S(0),S(m),S(n))    & \rightarrow & F(S(n),m,F(S(0),S(m),0)) \\
\text{(b6)} & F(S(S(x)),m,n)       & \rightarrow & F(S(0),m,F(S(x),m,n))
\end{array}
</math>
Instead of rule b6 one can define the rule 

<math display="block">
\begin{array}{lll}
\text{(b7)} & F(S(S(x)),m,n)       & \rightarrow & F(S(x),m,F(S(0),m,n))
\end{array}
</math>
To compute the Ackermann function it suffices to add three reduction rules

<math display="block"> 
\begin{array}{lll}
\text{(r8)}  & A(0,n)	     & \rightarrow & S(n) \\
\text{(r9)}  & A(S(m),n)     & \rightarrow & P(F(S(0),S(m),S(S(S(n))))) \\
\text{(r10)} & P(S(S(S(m)))) & \rightarrow & m \\
\end{array}
</math>

These rules take care of the base case A(0,n), the alignment (n+3) and the fudge (-3).

'''Example'''

Compute <math>A(2,1) \rightarrow_{*} 5</math>
{| style="border-collapse:collapse"
|style="text-align:left; border-right: solid thin black; padding-right: 0.5em"|using reduction rule <math>\text{b7}</math>:<ref group="n" name="letop1"/>{{space|4}}
|style="text-align:left;padding-left: 0.5em"|using reduction rule <math>\text{b6}</math>:<ref group="n" name="letop1"/>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|<math>\underline{A(2,1)}</math>
|style="padding-left: 0.5em"|<math>\underline{A(2,1)}</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{r9}  P(\underline{F(1,2,4)})</math>
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r9} P(\underline{F(1,2,4)})</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b5} P(F(4,1,\underline{F(1,2,0)}))</math>
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b5} P(F(4,1,\underline{F(1,2,0)}))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b3} P(\underline{F(4,1,0)})</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b3} P(\underline{F(4,1,0)})</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b7} P(F(3,1,\underline{F(1,1,0)}))</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,\underline{F(3,1,0)}))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b2} P(\underline{F(3,1,2)})</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,1,\underline{F(2,1,0)})))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b7} P(F(2,1,\underline{F(1,1,2)}))</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,1,F(1,1,\underline{F(1,1,0)}))))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b5} P(F(2,1,F(2,0,\underline{F(1,1,0)})))</math>{{space|10}}
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b2} P(F(1,1,F(1,1,\underline{F(1,1,2)})))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b2} P(F(2,1,\underline{F(2,0,2)}))</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b5} P(F(1,1,F(1,1,F(2,0,\underline{F(1,1,0)}))))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b7} P(F(2,1,F(1,0,\underline{F(1,0,2)})))</math> 
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b2} P(F(1,1,F(1,1,\underline{F(2,0,2)})))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(F(2,1,\underline{F(1,0,3)}))</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,1,F(1,0,\underline{F(1,0,2)}))))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(2,1,4)})</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,F(1,1,\underline{F(1,0,3)})))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b7} P(F(1,1,\underline{F(1,1,4)}))</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(1,1,4)}))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b5} P(F(1,1,F(4,0,\underline{F(1,1,0)})))</math> 
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b5} P(F(1,1,F(4,0,\underline{F(1,1,0)})))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b2} P(F(1,1,\underline{F(4,0,2)}))</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b2} P(F(1,1,\underline{F(4,0,2)}))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b7} P(F(1,1,F(3,0,\underline{F(1,0,2)})))</math> 
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,0,\underline{F(3,0,2)})))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(3,0,3)}))</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,0,F(1,0,\underline{F(2,0,2)}))))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b7} P(F(1,1,F(2,0,\underline{F(1,0,3)})))</math> 
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,0,F(1,0,F(1,0,\underline{F(1,0,2)})))))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(2,0,4)}))</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,F(1,0,F(1,0,\underline{F(1,0,3)}))))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b7} P(F(1,1,F(1,0,\underline{F(1,0,4)})))</math> 
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,F(1,0,\underline{F(1,0,4)})))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(1,0,5)}))</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(1,0,5)}))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(1,1,6)})</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(1,1,6)})</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b5} P(F(6,0,\underline{F(1,1,0)}))</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b5} P(F(6,0,\underline{F(1,1,0)}))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b2} P(\underline{F(6,0,2)})</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b2} P(\underline{F(6,0,2)})</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b7} P(F(5,0,\underline{F(1,0,2)}))</math> 		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,\underline{F(5,0,2)}))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(5,0,3)})</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,F(1,0,\underline{F(4,0,2)})))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b7} P(F(4,0,\underline{F(1,0,3)}))</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,F(1,0,F(1,0,\underline{F(3,0,2)}))))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(4,0,4)})</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,F(1,0,F(1,0,F(1,0,\underline{F(2,0,2)})))))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b7} P(F(3,0,\underline{F(1,0,4)}))</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,F(1,0,F(1,0,F(1,0,F(1,0,\underline{F(1,0,2)}))))))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(3,0,5)})</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(F(1,0,F(1,0,F(1,0,F(1,0,\underline{F(1,0,3)})))))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b7} P(F(2,0,\underline{F(1,0,5)}))</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(F(1,0,F(1,0,F(1,0,\underline{F(1,0,4)}))))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(2,0,6)})</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(F(1,0,F(1,0,\underline{F(1,0,5)})))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b7} P(F(1,0,\underline{F(1,0,6)}))</math>  		
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(F(1,0,\underline{F(1,0,6)}))</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(1,0,7)})</math>  					
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(1,0,7)})</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{b1} \underline{P(8)}</math>  							
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{b1} \underline{P(8)}</math>
|-
|style="border-right: solid thin black; padding-right: 0.5em"|{{space|4}}<math>\rightarrow_{r10} 5</math>											
|style="padding-left: 0.5em"|{{space|4}}<math>\rightarrow_{r10} 5</math>
|}

The matching equalities are
*when the TRS with the reduction rule <math>\text{b6}</math> is applied:

<math display="block">\begin{align}
& A(2,1) +3
= F(2,4)
= \dots
= F^6(0,2)
= F(0,F^5(0,2))
= F(0,F(0,F^4(0,2))) \\
& = F(0,F(0,F(0,F^3(0,2))))
= F(0,F(0,F(0,F(0,F^2(0,2)))))
= F(0,F(0,F(0,F(0,F(0,F(0,2)))))) \\
& = F(0,F(0,F(0,F(0,F(0,3)))))
= F(0,F(0,F(0,F(0,4))))
= F(0,F(0,F(0,5)))
= F(0,F(0,6))
= F(0,7)
= 8
\end{align}</math>
*when the TRS with the reduction rule <math>\text{b7}</math> is applied:

<math display="block">\begin{align}
& A(2,1) +3
= F(2,4)
= \dots
= F^6(0,2)
= F^5(0,F(0,2))
= F^5(0,3)
= F^4(0,F(0,3))
= F^4(0,4) \\
& = F^3(0,F(0,4))
= F^3(0,5)
= F^2(0,F(0,5))
= F^2(0,6)
= F(0,F(0,6))
= F(0,7)
= 8
\end{align}</math>
'''Remarks'''
*The computation of <math>\operatorname{A}_{i}(n)</math> according to the rules {b1 - b5, b6, r8 - r10} is deeply recursive. The maximum depth of nested <math>F</math>s is <math>A(i,n)+1</math>. The culprit is the order in which iteration is executed: <math>F^{n+1}(x) = F(F^{n}(x))</math>. The first <math>F</math> disappears only after the whole sequence is unfolded.
*The computation according to the rules {b1 - b5, b7, r8 - r10} is more efficient in that respect. The iteration <math>F^{n+1}(x) = F^{n}(F(x))</math> simulates the repeated loop over a block of code.<ref group="n" name="letop7">'''LOOP''' n+1 '''TIMES DO''' F</ref> The nesting is limited to <math>(i+1)</math>, one recursion level per iterated function. {{harvtxt|Meyer|Ritchie|1967}} showed this correspondence.
*These considerations concern the recursion depth only. Either way of iterating leads to the same number of reduction steps, involving the same rules (when the rules b6 and b7 are considered "the same"). The reduction of <math>A(2,1)</math> for instance converges in 35 steps: 12 × b1, 4 × b2, 1 × b3, 4 × b5, 12 × b6/b7, 1 × r9, 1 × r10. The ''modus iterandi'' only affects the order in which the reduction rules are applied.
*A real gain of execution time can only be achieved by not recalculating subresults over and over again. [[Memoization]] is an optimization technique where the results of function calls are cached and returned when the same inputs occur again. See for instance {{harvtxt|Ward|1993}}. {{harvtxt|Grossman|Zeitman|1988}} published a cunning algorithm which computes <math>A(i,n)</math> within <math>\mathcal{O}(i A(i,n))</math> time and within <math>\mathcal{O}(i)</math> space.

===Huge numbers===
To demonstrate how the computation of <math>A(4, 3)</math> results in many steps and in a large number:<ref group="n" name="letop1"/>


<math display="block">\begin{align}
A(4, 3) & \rightarrow A(3, A(4, 2)) \\
& \rightarrow A(3, A(3, A(4, 1))) \\
& \rightarrow A(3, A(3, A(3, A(4, 0)))) \\
& \rightarrow A(3, A(3, A(3, A(3, 1)))) \\
& \rightarrow A(3, A(3, A(3, A(2, A(3, 0))))) \\
& \rightarrow A(3, A(3, A(3, A(2, A(2, 1))))) \\
& \rightarrow A(3, A(3, A(3, A(2, A(1, A(2, 0)))))) \\
& \rightarrow A(3, A(3, A(3, A(2, A(1, A(1, 1)))))) \\
& \rightarrow A(3, A(3, A(3, A(2, A(1, A(0, A(1, 0))))))) \\
& \rightarrow A(3, A(3, A(3, A(2, A(1, A(0, A(0, 1))))))) \\
& \rightarrow A(3, A(3, A(3, A(2, A(1, A(0, 2)))))) \\
& \rightarrow A(3, A(3, A(3, A(2, A(1, 3))))) \\
& \rightarrow A(3, A(3, A(3, A(2, A(0, A(1, 2)))))) \\
& \rightarrow A(3, A(3, A(3, A(2, A(0, A(0, A(1, 1))))))) \\
& \rightarrow A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(1, 0)))))))) \\
& \rightarrow A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(0, 1)))))))) \\
& \rightarrow A(3, A(3, A(3, A(2, A(0, A(0, A(0, 2)) )) )) ) \\
& \rightarrow A(3, A(3, A(3, A(2, A(0, A(0, 3)))))) \\
& \rightarrow A(3, A(3, A(3, A(2, A(0, 4))))) \\
& \rightarrow A(3, A(3, A(3, A(2, 5)))) \\
& \qquad\vdots \\
& \rightarrow A(3, A(3, A(3, 13))) \\
& \qquad\vdots \\
& \rightarrow A(3, A(3, 65533)) \\
&\qquad\vdots \\
& \rightarrow A(3, 2^{65536} - 3) \\
&\qquad\vdots \\
& \rightarrow 2^{2^{65536}} - 3. \\
\end{align}</math>