Recursive definition of recursively defined operations

Question

The recursive definitions of addition, multiplication, and exponentiation usually stop after exponentiation ("${\small+}1$" to be read as "the successor of"):

$x \boldsymbol{+} (y\ {\small+}1) := (x \boldsymbol{+} y)\ {\small+}1$

$x \times (y\ {\small+}1) := (x \times y) \boldsymbol{+} x$

$x$ ^ $(y\ {\small+}1) := (x$ ^ $y) \times x$

Sometimes, this seems due to a lack of symbols, only. But it seems feasible to define a recursive sequence of operations $\circ_i$:

$x \circ_{i{\small+}1} (y\ {\small +}1) := (x \circ_{i{\small+}1} y) \circ_{i} x$

with

$x \circ_{0} y := x\ {\small+}1 $

Where resp. under which name is this sequence of operations investigated?

And:

Why is it - eventually - O.K. to stop after exponentiation?

Answer 1

It is called the Ackermann function (or some variant thereof).

http://en.wikipedia.org/wiki/Ackermann_function

Answer 2

As Stephen points out, these operations are given by the three-argument Ackermann function, plugging in 0 (for addition), 1 (for multiplication), etc. to the third argument.

Another notation used for the same thing is Knuth's up-arrow notation: it starts with $a \mathbin{\uparrow} b$ to denote $a^b$ and continues by denoting the next functions in the sequence with multiple arrows: $a \mathbin{\uparrow\uparrow} b$, $a \mathbin{\uparrow\uparrow\uparrow} b$, etc.