Hyper operator

Articleissues
OR=September 2008

The hyper operators forming the hyper"n" family are related to Knuth's up-arrow notation and Conway chained arrow notation as follows:

$extrm\{hyper\}\; n\; (a,\; b)\; =\; extrm\{hyper\}(a,n,b)\; =\; a\; uparrow^\{n-2\}\; b\; =\; a\; o\; b\; o\; (n-2)$.

This family of operators was described by Reuben Goodstein [Goodstein, R., "Transfinite Ordinals in Recursive Number Theory", Journal of Symbolic Logic, 12 (1947), 123-129 (see pp. 128-129).] , using the notation "G"("k","a","n") for what would here be written as hyper("a","k","n") or "a"^("k")"n", etc., "which is a variant of the Ackermann function". In the 1947 paper, Goodstein introduced the names "tetration", "pentation", "hexation", etc., for the successive operators beyond exponentiation. (More-recent publications refer to this entire family and its variants simply as the Ackermann hierarchy. [Harvey M. Friedman, "Long Finite Sequences", Journal of Combinatorial Theory, Series A, Volume 95, Issue 1, July 2001, Pages 102-144. [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHS-45RFJ9C-5&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_version=1&_urlVersion=0&_userid=10&md5=8097ac57c9dbe05b99fef6a95309f1df Online abstract] .] )

For example, with "n" = 4 we have hyper4 (tetration, super-exponentiation, power towers, etc.) in terms of an extension of standard operators:

$\{operatorname\{hyper4\}\; (a,\; b)\; =\; operatorname\{hyper\}(a,\; 4,\; b)\; =\; a\; ^\; \{(4)\}\; b\; =\; a\; uparrowuparrow\; b\; =\; atop\; \{\; !!!!!!!$underbrace{a^{a^{cdot^{cdot^{a atop {bmbox{ copies of }a !!!!!!!{=a o b o 2 atop {

See also Tables of values.

Derivation of the notation

It can be seen as an answer to the question "what's next in this sequence:
summation (+),
multiplication (×),
exponentiation (^),…?"Noting that
* $a\; +\; b\; =\; 1\; +\; (a\; +\; (b\; -\; 1))$
* $a\; imes\; b\; =\; a\; +\; (a\; imes\; (b\; -\; 1))$
* $a\; ^\; b\; =\; a\; imes\; (a\; ^\; \{(b\; -\; 1)\})$recursively define an
infix triadic operator (making n=0 correspond to the successor function):

then define$operatorname\{hypermathit\{n\; (a,\; b)\; =\; a\; ^\; \{(n)\}\; b$and$operatorname\{hyper\}(a,\; n,\; b)\; =\; a\; ^\; \{(n)\}\; b$

This gives:

$operatorname\{hyper1\}\; (a,\; b)\; =\; operatorname\{hyper\}(a,\; 1,\; b)\; =\; a\; ^\; \{(1)\}\; b\; =\; a+b$

$operatorname\{hyper2\}\; (a,\; b)\; =\; operatorname\{hyper\}(a,\; 2,\; b)\; =\; a\; ^\; \{(2)\}\; b\; =\; ab$

$operatorname\{hyper3\}\; (a,\; b)\; =\; operatorname\{hyper\}(a,\; 3,\; b)\; =\; a\; ^\; \{(3)\}\; b\; =\; a^b$

$\{operatorname\{hyper4\}\; (a,\; b)\; =\; operatorname\{hyper\}(a,\; 4,\; b)\; =\; a\; ^\; \{(4)\}\; b\; =\; a\; uparrowuparrow\; b\; =\; atop\; \{\; !!!!!!!$underbrace{a^{a^{cdot^{cdot^{a atop {bmbox{ copies of }a

as further explained in the separate article tetration.

Known aliases for hyper4 include superpower, superdegree, and powerlog; other notation,$operatorname\{hyper4\}(a,b)=\{\}^\{b\}a$.

The family has not been extended from natural numbers to real numbers in general for "n>3", due to nonassociativity in the "obvious" methods.

Evaluation from left to right

An alternative for these operators is obtained by evaluation from left to right. Since
* $a+b\; =\; (a+(b-1))+1$
* $a\; imes\; b\; =\; (a\; imes\; (b-1))+a$
* $a^b\; =\; (a^\{(b-1)\})\; imes\; a$define (with subscripts instead of superscripts)$a\_\{(n+1)\}b\; =\; (a\_\{(n+1)\}(b-1))\_\{(n)\}a$with $a\_\{(1)\}b\; =\; a+b$,$a\; \_\; \{(2)\}\; 0\; =\; 0$, and$a\; \_\; \{(n)\}\; 0\; =\; 1$for$n>2$

But this suffers a kind of collapse,failing to form the "power tower" traditionally expected of hyper4:$a\_\{(4)\}b\; =\; a^\{(a^\{(b-1)\})\}$

How can $a^\{(n)\}b$ be so different from $a\_\{(n)\}b$ for "n>3"? This is because of a symmetry called associativity that's "defined into" + and &times; (see field) but which ^ lacks. It is more apt to say the two "(n)"s were decreed to be the same for "n<4". (On the other hand, one can object that the field operations were defined to mimic what had been "observed in nature" and ask why "nature" suddenly objects to that symmetry&hellip;)

The other degrees do not collapse in this way, and so this family has some interest of its own as lower (perhaps lesser or inferior) hyper operators.

For example:

:moser = (..(2^^2)^^..2)^^2 (258 numbers 2)

Numeration systems based on hyper operations

Goodstein [1947] used what are here called hyper operators (in other notation) to create systems of numeration for the nonnegative integers. The so-called "complete hereditary representation" of integer "n", at level "k" and base "b", can be expressed as follows using only the first "k" hyper operators, written in the superscript notation defined earlier, and using as digits only 0, 1, ..., "b"-1:

* For 0 ≤ "n" ≤ "b"-1, "n" is represented simply by the corresponding digit.
* For "n" > "b"-1, the representation of "n" is found recursively, first representing "n" in the form :$b^\{(k)\}\{x\_k\}^\{(k-1)\}\{x\_\{k-1^\{(k-2)\}\; dots\; \{x\_2\}^\{(1)\}x\_1$:where "x"_"k", ..., "x"₁ are the largest integers satisfying (in turn)

:$b^\{(k)\}x\_k\; le\; n$

:$b^\{(k)\}\{x\_k\}^\{(k-1)\}x\_\{k-1\}\; le\; n$

:...

:$b^\{(k)\}\{x\_k\}^\{(k-1)\}\{x\_\{k-1^\{(k-2)\}\; dots\; \{x\_2\}^\{(1)\}x\_1\; le\; n$.

:Any "x"_"i" exceeding "b"-1 is then re-expressed in the same manner, and so on, repeating this procedure until the resulting form contains only the digits 0, 1, ..., "b"-1. Alternative notations for the underlying operator hierarchy could also be used, in which case the superscript $^\{(i)\}$ simply denotes the "i"^th operation in the hierarchy. For example, Knuth arrows (together with the usual + and &times; signs) can be used to denote this same hierarchy as $(\; +,\; imes,\; uparrow,\; uparrowuparrow,\; uparrowuparrowuparrow,\; dots)$, and are used freely in the remainder of this section. Unnecessary parentheses can be avoided by giving higher-level operators higher precedence in the order of evaluation; thus,

level-1 representations have the form $b\; +\; X$, with "X" also of this form;

level-2 representations have the form $b\; imes\; X\; +\; Y$, with "X","Y" also of this form;

level-3 representations have the form $b\; uparrow\; X\; imes\; Y\; +\; Z$, with "X","Y","Z" also of this form;

level-4 representations have the form $b\; uparrowuparrow\; X\; uparrow\; Y\; imes\; Z\; +\; T$, with "X","Y","Z","T" also of this form;

and so on.

The representations can be abbreviated by omitting any instances of $+0,\; imes1,\; uparrow1,\; uparrowuparrow1,$ etc.; for example, the level-3 base-2 representation of the number 6 is $2uparrow(2uparrow1\; imes1+0)\; imes1+(2uparrow1\; imes1+0)$, which abbreviates to $2\; uparrow\; 2\; +\; 2$.

Examples:The unique base-2 representations of the number 266, at levels 1, 2, 3, 4, and 5 are as follows:

:$ext\{Level\; 1:\}\; 266\; =\; 2\; +\; 2\; +\; dots\; +\; 2\; ext\{(with\; 133\; 2s)\}$:$ext\{Level\; 2:\}\; 266\; =\; 2\; imes\; (2\; imes\; (2\; imes\; (2\; imes\; 2\; imes\; 2\; imes\; 2\; imes\; 2\; +\; 1))\; +\; 1)$:$ext\{Level\; 3:\}\; 266\; =\; 2\; uparrow\; 2\; uparrow\; (2\; +\; 1)\; +\; 2\; uparrow\; (2\; +\; 1)\; +\; 2$:$ext\{Level\; 4:\}\; 266\; =\; 2\; uparrowuparrow\; (2\; +\; 1)\; uparrow\; 2\; +\; 2\; uparrowuparrow\; 2\; imes\; 2\; +\; 2$:$ext\{Level\; 5:\}\; 266\; =\; 2\; uparrowuparrowuparrow\; 2\; uparrowuparrow\; 2\; +\; 2\; uparrowuparrowuparrow\; 2\; imes\; 2\; +\; 2$.

ee also

* Ackermann function
* Tetration
* Knuth's up-arrow notation (note the Tables of values)
* Conway chained arrow notation

References