and : Of the various two-argument versions, the one developed by Péter and Robinson (called "the" Ackermann function by most authors) is defined for nonnegative integers and as follows: The Ackermann function has also been expressed in relation to the hyperoperation sequence: or, written in Knuth's up-arrow notation (extended to integer indices ): or, equivalently, in terms of Buck's function F: Definition: as iterated 1-ary function Define as the n-th iterate of : Iteration is the process of composing a function with itself a certain number of times. Function composition is an associative operation, so . Conceiving the Ackermann function as a sequence of unary functions, one can set . The function then becomes a sequence of unary functions, defined from iteration: Computation The recursive definition of the Ackermann function can naturally be transposed to a term rewriting system (TRS). TRS, based on 2-ary function The definition of the 2-ary Ackermann function leads to the obvious reduction rules Example Compute The reduction sequence is To compute one can use a stack, which initially contains the elements . Then repeatedly the two top elements are replaced according to the rules Schematically, starting from : WHILE stackLength <> 1 { POP 2 elements; PUSH 1 or 2 or 3 elements, applying the rules r1, r2, r3 } The pseudocode is published in . For example, on input , Remarks The leftmost-innermost strategy is implemented in 225 computer languages on Rosetta Code. For all the computation of takes no more than steps. pointed out that in the computation of the maximum length of the stack is , as long as . Their own algorithm, inherently iterative, computes within time and within space. TRS, based on iterated 1-ary function The definition of the iterated 1-ary Ackermann functions leads to different reduction rules As function composition is associative, instead of rule r6 one can define Like in the previous section the computation of can be implemented with a stack. Initially the stack contains the three elements . Then repeatedly the three top elements are replaced according to the rules Schematically, starting from : WHILE stackLength <> 1 { POP 3 elements; PUSH 1 or 3 or 5 elements, applying the rules r4, r5, r6; } Example On input the successive stack configurations are The corresponding equalities are When reduction rule r7 is used instead of rule r6, the replacements in the stack will follow The