Editing Ackermann function (section)

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