Editing Ackermann function (section)

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