A GENERALIZATION O F ACKERMANN'S FUNCTION by ROD MCBETH in Tehran (Iran) 8 1. Introduction
The sign Zf denotes the set of positive integers. The constant functions respectively always equal to 0, 1, 2, 3, . . . are denoted by 0, 1, 2, 3, . . , The identity function on Z+ is denoted by i. Now let E P be the class of polynomials of [2]. Let < be the relation of eventual domination between functions of EP, defined in
). Two further definitions may be made: g >f iff f < g, and f 5 g iff either f >g or f = g. By theorem 3.6 of [ 2 ] , E P contains no endlessly <-descending sequences of polynomials. Since < totally orders EP, < is thus by dpfinition a sequential ordering of EP. If e E E P satisfies e = 1, then e is the initial polynomial of EP. If e satisfies e = f + 1, f E EP, then e is a successor polynomial, written Suc(e). f is the predecessor of e and is written e-. If e does not satisfy e = f + 1 for any f E EP, and e is not the initial polynomial, then e is a diagonal polynomial, written Diag(e). The function g,,(x, y), first introduced by W. ACKERMANN [l], is defined by double recursion on the arguments y, n: 91("> Y) = x + Y, 9 / I + l ( ~> 1) = 5 7 v/ltl(x, Y + 1) = q&, 9/,+l(J4 y)), x, y, ?a E Z+. Hence g,(z, y) = xy, g,(x, y) = xu, g4(x, y) = x*Y (cf. [3]), etc., and gtIfl(x, 2 ) = grt(x, 2). The function of one argument is defined from the function of three arguments by identification of arguments : q ( x ) = Vl(x9 The function of three arguments, and related functions, are discussed in [4, pp. 82-88], [5, pp. 103-1101 and [6].