Editing Ackermann function (section)

===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.