# Tetration

In mathematics, tetration (or hyper-4) is iterated, or repeated, exponentiation. It is the next hyperoperation after exponentiation, but before pentation. The word was coined by Reuben Louis Goodstein from tetra- (four) and iteration. Tetration is used for the notation of very large numbers. The notation ${\displaystyle {^{n}a}}$ means ${\displaystyle {a^{a^{\cdot ^{\cdot ^{a}}}}}}$, which is the application of exponentiation ${\displaystyle n-1}$ times.

The first four hyperoperations are shown here, with tetration being the fourth of these (in this case, the unary operation succession, ${\displaystyle a'=a+1}$, is considered to be the zeroth operation).

${\displaystyle a+n=a+\underbrace {1+1+\cdots +1} _{n}}$
n copies of 1 added to a.
2. Multiplication
${\displaystyle a\times n=\underbrace {a+a+\cdots +a} _{n}}$
n copies of a combined by addition.
3. Exponentiation
${\displaystyle a^{n}=\underbrace {a\times a\times \cdots \times a} _{n}}$
n copies of a combined by multiplication.
4. Tetration
${\displaystyle {^{n}a}=\underbrace {a^{a^{\cdot ^{\cdot ^{a}}}}} _{n}}$
n copies of a combined by exponentiation, right-to-left.

Here, succession (a' = a + 1) is the most basic operation; addition (a + n) is a primary operation, though for natural numbers it can be thought of as a chained succession of n successors of a; multiplication (${\displaystyle a\times n}$) is also a primary operation, though for natural numbers it can be thought of as a chained addition involving n numbers a. Exponentiation (${\displaystyle a^{n}}$) can be thought of as a chained multiplication involving n numbers a, and analogously, tetration (${\displaystyle ^{n}a}$) can be thought of as a chained power involving n numbers a. Each of the operations above are defined by iterating the previous one; however, unlike the operations before it, tetration is not an elementary function.

The parameter a may be called the base-parameter in the following, while the parameter n in the following may be called the height-parameter (which is integral in the first approach but may be generalized to fractional, real and complex heights, see below). Tetration is read as "the nth tetration of a".

Domain coloring of the holomorphic tetration ${\displaystyle {}^{z}e}$, with hue representing the function argument and brightness representing magnitude
${\displaystyle {}^{n}x}$, for n = 2, 3, 4 ..., showing convergence to the infinitely iterated exponential between the two dots

## Formal definition

For any positive real ${\displaystyle a>0}$ and non-negative integer ${\displaystyle n\geq 0}$, we can define ${\displaystyle \,\!{^{n}a}}$ recursively as:

${\displaystyle {^{n}a}:={\begin{cases}1&{\text{if }}n=0\\a^{\left(^{(n-1)}a\right)}&{\text{if }}n>0\end{cases}}}$

This formal definition is equivalent to repeated exponentiation for natural heights; however, this definition allows for extensions to other heights such as ${\displaystyle ^{0}a}$, ${\displaystyle ^{-1}a}$, and ${\displaystyle ^{i}a}$.

## Terminology

There are many terms for tetration, each of which has some logic behind it, but some have not become commonly used for one reason or another. Here is a comparison of each term with its rationale and counter-rationale.

• The term tetration, introduced by Goodstein in his 1947 paper Transfinite Ordinals in Recursive Number Theory[1] (generalizing the recursive base-representation used in Goodstein's theorem to use higher operations), has gained dominance. It was also popularized in Rudy Rucker's Infinity and the Mind.
• The term superexponentiation was published by Bromer in his paper Superexponentiation in 1987.[2] It was used earlier by Ed Nelson in his book Predicative Arithmetic, Princeton University Press, 1986.
• The term hyperpower[3] is a natural combination of hyper and power, which aptly describes tetration. The problem lies in the meaning of hyper with respect to the hyperoperation sequence. When considering hyperoperations, the term hyper refers to all ranks, and the term super refers to rank 4, or tetration. So under these considerations hyperpower is misleading, since it is only referring to tetration.
• The term power tower[4] is occasionally used, in the form "the power tower of order n" for ${\displaystyle {\ \atop {\ }}{{\underbrace {a^{a^{\cdot ^{\cdot ^{a}}}}} } \atop n}}$. This is a misnomer, however, because tetration cannot be expressed with iterated power functions (see above), since it is an iterated exponential function.
• The term snap is occasionally used in informal contexts, in the form "a snap n" for ${\displaystyle {\ \atop {\ }}{{\underbrace {a^{a^{\cdot ^{\cdot ^{a}}}}} } \atop n}}$. This term is not yet widely accepted, although it is used within select communities. It is believed to be a reference to jounce, the fourth derivative of position in physics, as tetration is the fourth hyperoperation and jounce is also known as snap.

Owing in part to some shared terminology and similar notational symbolism, tetration is often confused with closely related functions and expressions. Here are a few related terms:

Form Terminology
${\displaystyle a^{a^{\cdot ^{\cdot ^{a^{a}}}}}}$ Tetration
${\displaystyle a^{a^{\cdot ^{\cdot ^{a^{x}}}}}}$ Iterated exponentials
${\displaystyle a_{1}^{a_{2}^{\cdot ^{\cdot ^{a_{n}}}}}}$ Nested exponentials (also towers)
${\displaystyle a_{1}^{a_{2}^{a_{3}^{\cdot ^{\cdot ^{\cdot }}}}}}$ Infinite exponentials (also towers)

In the first two expressions a is the base, and the number of times a appears is the height (add one for x). In the third expression, n is the height, but each of the bases is different.

Care must be taken when referring to iterated exponentials, as it is common to call expressions of this form iterated exponentiation, which is ambiguous, as this can either mean iterated powers or iterated exponentials.

## Notation

There are many different notation styles that can be used to express tetration. Some notations can also be used to describe other hyperoperations, while some are limited to tetration and have no immediate extension.

Name Form Description
Rudy Rucker notation ${\displaystyle \,{}^{n}a}$ Used by Maurer [1901] and Goodstein [1947]; Rudy Rucker's book Infinity and the Mind popularized the notation.
Knuth's up-arrow notation ${\displaystyle a{\uparrow \uparrow }n}$ Allows extension by putting more arrows, or, even more powerfully, an indexed arrow.
Conway chained arrow notation ${\displaystyle a\rightarrow n\rightarrow 2}$ Allows extension by increasing the number 2 (equivalent with the extensions above), but also, even more powerfully, by extending the chain
Ackermann function ${\displaystyle {}^{n}2=\operatorname {A} (4,n-3)+3}$ Allows the special case ${\displaystyle a=2}$ to be written in terms of the Ackermann function.
Iterated exponential notation ${\displaystyle \exp _{a}^{n}(1)}$ Allows simple extension to iterated exponentials from initial values other than 1.
Hooshmand notations[5] {\displaystyle {\begin{aligned}&\operatorname {uxp} _{a}n\\[2pt]&a^{\frac {n}{}}\end{aligned}}} Used by M. H. Hooshmand [2006].
Hyperoperation notations {\displaystyle {\begin{aligned}&a[4]n\\[2pt]&H_{4}(a,n)\end{aligned}}} Allows extension by increasing the number 4; this gives the family of hyperoperations.
Double caret notation a^^n Since the up-arrow is used identically to the caret (^), tetration may be written as (^^); convenient for ASCII.
Bowers's operators
• {a,b,4}
• {a,b,4,1}
• a {4} b
Similar to the hyperoperation notations.

One notation above uses iterated exponential notation; in general this is defined as follows:

${\displaystyle \exp _{a}^{n}(x)=a^{a^{\cdot ^{\cdot ^{a^{x}}}}}}$ with n "a"s.

There are not as many notations for iterated exponentials, but here are a few:

Name Form Description
Standard notation ${\displaystyle \exp _{a}^{n}(x)}$ Euler coined the notation ${\displaystyle \exp _{a}(x)=a^{x}}$, and iteration notation ${\displaystyle f^{n}(x)}$ has been around about as long.
Knuth's up-arrow notation ${\displaystyle (a{\uparrow })^{n}(x)}$ Allows for super-powers and super-exponential function by increasing the number of arrows; used in the article on large numbers.
Text notation exp_a^n(x) Based on standard notation; convenient for ASCII.
J Notation x^^:(n-1)x Repeats the exponentiation. See J (programming language)[6]

## Examples

Because of the extremely fast growth of tetration, most values in the following table are too large to write in scientific notation. In these cases, iterated exponential notation is used to express them in base 10. The values containing a decimal point are approximate.

${\displaystyle x}$ ${\displaystyle {}^{2}x}$ ${\displaystyle {}^{3}x}$ ${\displaystyle {}^{4}x}$ ${\displaystyle {}^{5}x}$
1 1 1 1 1
2 4 16 65,536 265,536 or (2.00353 × 1019,728)
3 27 7,625,597,484,987 ${\displaystyle \exp _{10}^{3}(1.09902)}$ (3.6 × 1012 digits) ${\displaystyle \exp _{10}^{4}(1.09902)}$
4 256 1.34078 × 10154 ${\displaystyle \exp _{10}^{3}(2.18726)}$ (8.1 × 10153 digits) ${\displaystyle \exp _{10}^{4}(2.18726)}$
5 3,125 1.91101 × 102,184 ${\displaystyle \exp _{10}^{3}(3.33928)}$ (1.3 × 102,184 digits) ${\displaystyle \exp _{10}^{4}(3.33928)}$
6 46,656 2.65912 × 1036,305 ${\displaystyle \exp _{10}^{3}(4.55997)}$ (2.1 × 1036,305 digits) ${\displaystyle \exp _{10}^{4}(4.55997)}$
7 823,543 3.75982 × 10695,974 ${\displaystyle \exp _{10}^{3}(5.84259)}$ (3.2 × 10695,974 digits) ${\displaystyle \exp _{10}^{4}(5.84259)}$
8 16,777,216 6.01452 × 1015,151,335 ${\displaystyle \exp _{10}^{3}(7.18045)}$ (5.4 × 1015,151,335 digits) ${\displaystyle \exp _{10}^{4}(7.18045)}$
9 387,420,489 4.28125 × 10369,693,099 ${\displaystyle \exp _{10}^{3}(8.56784)}$ (4.1 × 10369,693,099 digits) ${\displaystyle \exp _{10}^{4}(8.56784)}$
10 10,000,000,000 1010,000,000,000 ${\displaystyle \exp _{10}^{3}(10)}$ (101010 digits) ${\displaystyle \exp _{10}^{4}(10)}$

## Properties

Tetration has several properties that are similar to exponentiation, as well as properties that are specific to the operation and are lost or gained from exponentiation. Because exponentiation does not commute, the product and power rules do not have an analogue with tetration; the statements ${\textstyle {}^{a}\left({}^{b}x\right)=\left({}^{ab}x\right)}$ and ${\textstyle {}^{a}\left(xy\right)={}^{a}x{}^{a}y}$ are not necessarily true for all cases.[7]

However, tetration does follow a different property, in which ${\textstyle {}^{a}x=x^{\left({}^{a-1}x\right)}}$. This fact is most clearly shown using the recursive definition. From this property, a proof follows that ${\displaystyle \left({}^{b}a\right)^{\left({}^{c}a\right)}=\left({}^{c+1}a\right)^{\left({}^{b-1}a\right)}}$, which allows for switching b and c in certain equations. The proof goes as follows:

{\displaystyle {\begin{aligned}&\left({}^{b}a\right)^{\left({}^{c}a\right)}\\={}&\left(a^{{}^{b-1}a}\right)^{\left({}^{c}a\right)}\\={}&a^{\left({}^{b-1}a\right)\left({}^{c}a\right)}\\={}&a^{\left({}^{c}a\right)\left({}^{b-1}a\right)}\\={}&\left({}^{c+1}a\right)^{\left({}^{b-1}a\right)}\end{aligned}}}

When a number x and 10 are coprime, it is possible to compute the last m decimal digits of ${\displaystyle \,\!\ ^{a}x}$ using Euler's theorem, for any integer m.

### Direction of evaluation

When evaluating tetration expressed as an "exponentiation tower", the exponentiation is done at the deepest level first (in the notation, at the apex). For example:

${\displaystyle \,\!\ ^{4}2=2^{2^{2^{2}}}=2^{\left(2^{\left(2^{2}\right)}\right)}=2^{\left(2^{4}\right)}=2^{16}=65,\!536}$

This order is important because exponentiation is not associative, and evaluating the expression in the opposite order will lead to a different answer:

${\displaystyle \,\!2^{2^{2^{2}}}\neq \left({\left(2^{2}\right)}^{2}\right)^{2}=4^{2\cdot 2}=256}$

Evaluating the expression the left to right is considered less interesting; evaluating left to right, any expression ${\displaystyle ^{n}a}$ can be simplified to be ${\displaystyle a^{\left(a^{n-1}\right)}}$.[8] Because of this, the towers must be evaluated from right to left (or top to bottom). Computer programmers refer to this choice as right-associative.

## Extensions

Tetration can be extended in two different ways; in the equation ${\displaystyle ^{n}a}$, both the base a and the height n can be generalized using the definition and properties of tetration. Although the base and the height can be extended beyond the positive integers to different domains, including ${\displaystyle {^{n}0}}$, complex functions such as ${\displaystyle {}^{n}i}$, and heights of infinite ${\displaystyle n}$, the more limited properties of tetration reduce the ability to extend tetration.

### Extension of domain for bases

#### Base zero

The exponential ${\displaystyle 0^{0}}$ is not consistently defined. Thus, the tetrations ${\displaystyle \,{^{n}0}}$ are not clearly defined by the formula given earlier. However, ${\displaystyle \lim _{x\rightarrow 0}{}^{n}x}$ is well defined, and exists:

${\displaystyle \lim _{x\rightarrow 0}{}^{n}x={\begin{cases}1,&n{\text{ even}}\\0,&n{\text{ odd}}\end{cases}}}$

Thus we could consistently define ${\displaystyle {}^{n}0=\lim _{x\rightarrow 0}{}^{n}x}$. This is equivalent to defining ${\displaystyle 0^{0}=1}$.

Under this extension, ${\displaystyle {}^{0}0=1}$, so the rule ${\displaystyle {^{0}a}=1}$ from the original definition still holds.

#### Complex bases

Tetration by period
Tetration by escape

Since complex numbers can be raised to powers, tetration can be applied to bases of the form z = a + bi (where a and b are real). For example, in nz with z = i, tetration is achieved by using the principal branch of the natural logarithm; using Euler's formula we get the relation:

${\displaystyle i^{a+bi}=e^{{\frac {1}{2}}{\pi i}(a+bi)}=e^{-{\frac {1}{2}}{\pi b}}\left(\cos {\frac {\pi a}{2}}+i\sin {\frac {\pi a}{2}}\right)}$

This suggests a recursive definition for n+1i = a' + b'i given any ni = a + bi:

{\displaystyle {\begin{aligned}a'&=e^{-{\frac {1}{2}}{\pi b}}\cos {\frac {\pi a}{2}}\\[2pt]b'&=e^{-{\frac {1}{2}}{\pi b}}\sin {\frac {\pi a}{2}}\end{aligned}}}

The following approximate values can be derived:

${\textstyle {}^{n}i}$ Approximate value
${\textstyle {}^{1}i=i}$ i
${\textstyle {}^{2}i=i^{\left({}^{1}i\right)}}$ 0.2079
${\textstyle {}^{3}i=i^{\left({}^{2}i\right)}}$ 0.9472 + 0.3208i
${\textstyle {}^{4}i=i^{\left({}^{3}i\right)}}$ 0.0501 + 0.6021i
${\textstyle {}^{5}i=i^{\left({}^{4}i\right)}}$ 0.3872 + 0.0305i
${\textstyle {}^{6}i=i^{\left({}^{5}i\right)}}$ 0.7823 + 0.5446i
${\textstyle {}^{7}i=i^{\left({}^{6}i\right)}}$ 0.1426 + 0.4005i
${\textstyle {}^{8}i=i^{\left({}^{7}i\right)}}$ 0.5198 + 0.1184i
${\textstyle {}^{9}i=i^{\left({}^{8}i\right)}}$ 0.5686 + 0.6051i

Solving the inverse relation, as in the previous section, yields the expected 0i = 1 and −1i = 0, with negative values of n giving infinite results on the imaginary axis. Plotted in the complex plane, the entire sequence spirals to the limit 0.4383 + 0.3606i, which could be interpreted as the value where n is infinite.

Such tetration sequences have been studied since the time of Euler, but are poorly understood due to their chaotic behavior. Most published research historically has focused on the convergence of the infinitely iterated exponential function. Current research has greatly benefited by the advent of powerful computers with fractal and symbolic mathematics software. Much of what is known about tetration comes from general knowledge of complex dynamics and specific research of the exponential map.

### Extensions of the domain for different "heights"

#### Infinite heights

${\displaystyle \textstyle \lim _{n\rightarrow \infty }{}^{n}x}$ of the infinitely iterated exponential converges for the bases ${\displaystyle \textstyle \left(e^{-1}\right)^{e}\leq x\leq e^{\left(e^{-1}\right)}}$
The function ${\displaystyle \left|{\frac {\mathrm {W} (-\ln {z})}{-\ln {z}}}\right|}$ on the complex plane, showing the real-valued infinitely iterated exponential function (black curve)

Tetration can be extended to infinite heights;[9] i.e., for certain a and n values in ${\displaystyle {}^{n}a}$, there exists a well defined result for an infinite n. This is because for bases within a certain interval, tetration converges to a finite value as the height tends to infinity. For example, ${\displaystyle {\sqrt {2}}^{{\sqrt {2}}^{{\sqrt {2}}^{\cdot ^{\cdot ^{\cdot }}}}}}$ converges to 2, and can therefore be said to be equal to 2. The trend towards 2 can be seen by evaluating a small finite tower:

{\displaystyle {\begin{aligned}{\sqrt {2}}^{{\sqrt {2}}^{{\sqrt {2}}^{{\sqrt {2}}^{{\sqrt {2}}^{1.414}}}}}&\approx {\sqrt {2}}^{{\sqrt {2}}^{{\sqrt {2}}^{{\sqrt {2}}^{1.63}}}}\\&\approx {\sqrt {2}}^{{\sqrt {2}}^{{\sqrt {2}}^{1.76}}}\\&\approx {\sqrt {2}}^{{\sqrt {2}}^{1.84}}\\&\approx {\sqrt {2}}^{1.89}\\&\approx 1.93\end{aligned}}}

In general, the infinitely iterated exponential ${\displaystyle x^{x^{\cdot ^{\cdot ^{\cdot }}}}}$, defined as the limit of ${\displaystyle {}^{n}x}$ as n goes to infinity, converges for ee ≤ x ≤ e1/e, roughly the interval from 0.066 to 1.44, a result shown by Leonhard Euler.[10] The limit, should it exist, is a positive real solution of the equation y = xy. Thus, x = y1/y. The limit defining the infinite tetration of x fails to converge for x > e1/e because the maximum of y1/y is e1/e.

This may be extended to complex numbers z with the definition:

${\displaystyle {}^{\infty }z=z^{z^{\cdot ^{\cdot ^{\cdot }}}}={\frac {\mathrm {W} (-\ln {z})}{-\ln {z}}}~,}$

where W represents Lambert's W function.

As the limit y = x (if existent, i.e. for ee < x < e1/e) must satisfy xy = y we see that x ↦ y = x is (the lower branch of) the inverse function of y ↦ x = y1/y.

#### Negative heights

We can use the recursive rule for tetration,

${\displaystyle {^{k+1}a}=a^{\left({^{k}a}\right)},}$

to prove ${\displaystyle {}^{-1}a}$:

${\displaystyle ^{k}a=\log _{a}\left(^{k+1}a\right);}$

Substituting −1 for k gives

${\displaystyle {}^{-1}a=\log _{a}\left({}^{0}a\right)=\log _{a}1=0}$.[8]

Smaller negative values cannot be well defined in this way. Substituting −2 for k in the same equation gives

${\displaystyle {}^{-2}a=\log _{a}\left({}^{-1}a\right)=\log _{a}0}$

which is not well defined. They can, however, sometimes be considered sets.[8]

For ${\displaystyle n=1}$, any definition of ${\displaystyle \,\!{^{-1}1}}$ is consistent with the rule because

${\displaystyle {^{0}1}=1=1^{n}}$ for any ${\displaystyle \,\!n={^{-1}1}}$.

#### Real heights

At this time there is no commonly accepted solution to the general problem of extending tetration to the real or complex values of ${\displaystyle n}$. There have, however, been multiple approaches towards the issue, and different approaches are outlined below.

In general the problem is finding, for any real a > 0, a super-exponential function ${\displaystyle \,f(x)={}^{x}a}$ over real x > −2 that satisfies

• ${\displaystyle \,{}^{-1}a=0}$
• ${\displaystyle \,{}^{0}a=1}$
• ${\displaystyle \,{}^{x}a=a^{\left({}^{x-1}a\right)}}$for all real ${\displaystyle x>-1.}$[11]

To find a more natural extension, one or more extra requirements are usually required. This is usually some collection of the following:

• A continuity requirement (usually just that ${\displaystyle {}^{x}a}$ is continuous in both variables for ${\displaystyle x>0}$).
• A differentiability requirement (can be once, twice, k times, or infinitely differentiable in x).
• A regularity requirement (implying twice differentiable in x) that:
${\displaystyle \left({\frac {d^{2}}{dx^{2}}}f(x)>0\right)}$ for all ${\displaystyle x>0}$

The fourth requirement differs from author to author, and between approaches. There are two main approaches to extending tetration to real heights; one is based on the regularity requirement, and one is based on the differentiability requirement. These two approaches seem to be so different that they may not be reconciled, as they produce results inconsistent with each other.

When ${\displaystyle \,{}^{x}a}$ is defined for an interval of length one, the whole function easily follows for all x > −2.

${\displaystyle \,{}^{x}e}$ using linear approximation.

A linear approximation (solution to the continuity requirement, approximation to the differentiability requirement) is given by:

${\displaystyle {}^{x}a\approx {\begin{cases}\log _{a}\left(^{x+1}a\right)&x\leq -1\\1+x&-1

hence:

Approximation Domain
${\textstyle {}^{x}a\approx x+1}$ for −1 < x < 0
${\textstyle {}^{x}a\approx a^{x}}$ for 0 < x < 1
${\textstyle {}^{x}a\approx a^{a^{(x-1)}}}$ for 1 < x < 2

and so on. However, it is only piecewise differentiable; at integer values of x the derivative is multiplied by ${\displaystyle \ln {a}}$. It is continuously differentiable for ${\displaystyle x>-2}$ if and only if ${\displaystyle a=e}$. For example, using these methods ${\displaystyle {}^{\frac {\pi }{2}}e\approx 5.868...}$ and ${\displaystyle {}^{-4.3}0.5\approx 4.03335...}$

A main theorem in Hooshmand's paper[5] states: Let ${\displaystyle 0. If ${\displaystyle f:(-2,+\infty )\rightarrow \mathbb {R} }$ is continuous and satisfies the conditions:

• ${\displaystyle f(x)=a^{f(x-1)}\;\;{\text{for all}}\;\;x>-1,\;f(0)=1,}$
• ${\displaystyle f}$ is differentiable on ${\displaystyle (-1,0),}$
• ${\displaystyle f^{\prime }}$ is a nondecreasing or nonincreasing function on ${\displaystyle (-1,0),}$
• ${\displaystyle f^{\prime }\left(0^{+}\right)=(\ln a)f^{\prime }\left(0^{-}\right){\text{ or }}f^{\prime }\left(-1^{+}\right)=f^{\prime }\left(0^{-}\right).}$

then ${\displaystyle f}$ is uniquely determined through the equation

${\displaystyle f(x)=\exp _{a}^{[x]}\left(a^{(x)}\right)=\exp _{a}^{[x+1]}((x))\quad {\text{for all}}\;\;x>-2,}$

where ${\displaystyle (x)=x-[x]}$ denotes the fractional part of x and ${\displaystyle \exp _{a}^{[x]}}$ is the ${\displaystyle [x]}$-iterated function of the function ${\displaystyle \exp _{a}}$.

The proof is that the second through fourth conditions trivially imply that f is a linear function on [−1, 0].

The linear approximation to natural tetration function ${\displaystyle {}^{x}e}$ is continuously differentiable, but its second derivative does not exist at integer values of its argument. Hooshmand derived another uniqueness theorem for it which states:

If ${\displaystyle f:(-2,+\infty )\rightarrow \mathbb {R} }$ is a continuous function that satisfies:

• ${\displaystyle f(x)=e^{f(x-1)}\;\;{\text{for all}}\;\;x>-1,\;f(0)=1,}$
• ${\displaystyle f}$ is convex on ${\displaystyle (-1,0),}$
• ${\displaystyle f^{\prime }\left(0^{-}\right)\leq f^{\prime }\left(0^{+}\right).}$

then ${\displaystyle f={\text{uxp}}}$. [Here ${\displaystyle f={\text{uxp}}}$ is Hooshmand's name for the linear approximation to the natural tetration function.]

The proof is much the same as before; the recursion equation ensures that ${\displaystyle f^{\prime }(-1^{+})=f^{\prime }(0^{+}),}$ and then the convexity condition implies that ${\displaystyle f}$ is linear on (−1, 0).

Therefore, the linear approximation to natural tetration is the only solution of the equation ${\displaystyle f(x)=e^{f(x-1)}\;\;(x>-1)}$ and ${\displaystyle f(0)=1}$ which is convex on ${\displaystyle (-1,+\infty )}$. All other sufficiently-differentiable solutions must have an inflection point on the interval (−1, 0).

a comparison of the linear and quadratic approximations (in red and blue respectively) of the function ${\displaystyle ^{x}0.5}$, from x = –2 to x = 2.

Beyond linear approximations, a quadratic approximation (to the differentiability requirement) is given by:

${\displaystyle {}^{x}a\approx {\begin{cases}\log _{a}\left({}^{x+1}a\right)&x\leq -1\\1+{\frac {2\ln(a)}{1\;+\;\ln(a)}}x-{\frac {1\;-\;\ln(a)}{1\;+\;\ln(a)}}x^{2}&-10\end{cases}}}$

which is differentiable for all ${\displaystyle x>0}$, but not twice differentiable. For example, ${\displaystyle {}^{\frac {1}{2}}2\approx 1.45933...}$ If ${\displaystyle a=e}$ this is the same as the linear approximation.[12]

Note that because of the way it is calculated, this function does not "cancel out", contrary to exponents, where ${\displaystyle \left(a^{\frac {1}{n}}\right)^{n}=a}$. Namely,

${\displaystyle {}^{n}\left({}^{\frac {1}{n}}a\right)=\underbrace {\left({}^{\frac {1}{n}}a\right)^{\left({}^{\frac {1}{n}}a\right)^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\left({}^{\frac {1}{n}}a\right)}}}}}}} _{n}\neq a}$.

Just as there is a quadratic approximation, cubic approximations and methods for generalizing to approximations of degree n also exist, although they are much more unwieldy.[12][13]

#### Complex heights

Drawing of the analytic extension ${\displaystyle f=F(x+{\rm {i}}y)}$ of tetration to the complex plane. Levels ${\displaystyle |f|=1,e^{\pm 1},e^{\pm 2},\ldots }$ and levels ${\displaystyle \arg(f)=0,\pm 1,\pm 2,\ldots }$ are shown with thick curves.

It has now been proven[14] that there exists a unique function F which is a solution of the equation F(z + 1) = exp(F(z)) and satisfies the additional conditions that F(0) = 1 and F(z) approaches the fixed points of the logarithm (roughly 0.318 ± 1.337i) as z approaches ±i∞ and that F is holomorphic in the whole complex z-plane, except the part of the real axis at z ≤ −2. This proof confirms a previous conjecture.[15] The complex map of this function is shown in the figure at right. The proof also works for other bases besides e, as long as the base is bigger than ${\displaystyle e^{\frac {1}{e}}}$. The complex double precision approximation of this function is available online.

The requirement of the tetration being holomorphic is important for its uniqueness. Many functions ${\displaystyle S}$ can be constructed as

${\displaystyle S(z)=F\!\left(~z~+\sum _{n=1}^{\infty }\sin(2\pi nz)~\alpha _{n}+\sum _{n=1}^{\infty }{\Big (}1-\cos(2\pi nz){\Big )}~\beta _{n}\right)}$

where ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ are real sequences which decay fast enough to provide the convergence of the series, at least at moderate values of ${\displaystyle \Im (z)}$.

The function S satisfies the tetration equations S(z + 1) = exp(S(z)), S(0) = 1, and if αn and βn approach 0 fast enough it will be analytic on a neighborhood of the positive real axis. However, if some elements of {α} or {β} are not zero, then function S has multitudes of additional singularities and cutlines in the complex plane, due to the exponential growth of sin and cos along the imaginary axis; the smaller the coefficients {α} and {β} are, the further away these singularities are from the real axis.

The extension of tetration into the complex plane is thus essential for the uniqueness; the real-analytic tetration is not unique.

## Non-elementary recursiveness

Tetration (restricted to ${\displaystyle \mathbb {N} ^{2}}$) is not an elementary recursive function. One can prove by induction that for every elementary recursive function f, there is a constant c such that

${\displaystyle f(x)\leq \underbrace {2^{2^{\cdot ^{\cdot ^{x}}}}} _{c}.}$

We denote the right hand side by ${\displaystyle g(c,x)}$. Suppose on the contrary that tetration is elementary recursive. ${\displaystyle g(x,x)+1}$ is also elementary recursive. By the above inequality, there is a constant c such that ${\displaystyle g(x,x)+1\leq g(c,x)}$. By letting ${\displaystyle x=c}$, we have that ${\displaystyle g(c,c)+1\leq g(c,c)}$, a contradiction.

## Inverse operations

Exponentiation has two inverse operations; roots and logarithms. Analogously, the inverses of tetration are often called the super-root, and the super-logarithm (In fact, all hyperoperations greater than or equal to 3 have analogous inverses); e.g., in the function ${\displaystyle {^{3}}y=x}$, the two inverses are the cube super-root of y and the super logarithm base y of x.

### Super-root

The super-root is the inverse operation of tetration with respect to the base: if ${\displaystyle ^{n}y=x}$, then y is an nth super root of x (${\displaystyle {\sqrt[{n}]{x}}_{s}}$ or ${\displaystyle {\sqrt[{n}]{x}}_{4}}$).

For example,

${\displaystyle ^{4}2=2^{2^{2^{2}}}=65,536}$

so 2 is the 4th super-root of 65,536.

#### Square super-root

The graph y = ${\displaystyle {\sqrt {x}}_{s}}$.

The 2nd-order super-root, square super-root, or super square root has two equivalent notations, ${\displaystyle \mathrm {ssrt} (x)}$ and ${\displaystyle {\sqrt {x}}_{s}}$. It is the inverse of ${\displaystyle ^{2}x=x^{x}}$ and can be represented with the Lambert W function:[16]

${\displaystyle \mathrm {ssrt} (x)=e^{W(\mathrm {ln} (x))}={\frac {\mathrm {ln} (x)}{W(\mathrm {ln} (x))}}}$

The function also illustrates the reflective nature of the root and logarithm functions as the equation below only holds true when ${\displaystyle y=\mathrm {ssrt} (x)}$:

${\displaystyle {\sqrt[{y}]{x}}=\log _{y}x}$

Like square roots, the square super-root of x may not have a single solution. Unlike square roots, determining the number of square super-roots of x may be difficult. In general, if ${\displaystyle e^{-1/e}, then x has two positive square super-roots between 0 and 1; and if ${\displaystyle x>1}$, then x has one positive square super-root greater than 1. If x is positive and less than ${\displaystyle e^{-1/e}}$ it doesn't have any real square super-roots, but the formula given above yields countably infinitely many complex ones for any finite x not equal to 1.[16] The function has been used to determine the size of data clusters.[17]

#### Other super-roots

The graph ${\displaystyle y={\sqrt[{3}]{x}}_{s}}$.

For each integer n > 2, the function nx is defined and increasing for x ≥ 1, and n1 = 1, so that the nth super-root of x, ${\displaystyle {\sqrt[{n}]{x}}_{s}}$, exists for x ≥ 1.

However, if the linear approximation above is used, then ${\displaystyle ^{y}x=y+1}$ if −1 < y ≤ 0, so ${\displaystyle ^{y}{\sqrt {y+1}}_{s}}$ cannot exist.

In the same way as the square super-root, terminology for other super roots can be based on the normal roots: "cube super-roots" can be expressed as ${\displaystyle {\sqrt[{3}]{x}}_{s}}$; the "4th super-root" can be expressed as ${\displaystyle {\sqrt[{4}]{x}}_{s}}$; and the "nth super-root" is ${\displaystyle {\sqrt[{n}]{x}}_{s}}$. Note that ${\displaystyle {\sqrt[{n}]{x}}_{s}}$ may not be uniquely defined, because there may be more than one nth root. For example, x has a single (real) super-root if n is odd, and up to two if n is even.

Just as with the extension of tetration to infinite heights, the super-root can be extended to ${\displaystyle n=\infty }$, being well-defined if 1/exe. Note that ${\displaystyle x={^{\infty }y}=y^{\left[^{\infty }y\right]}=y^{x},}$ and thus that ${\displaystyle y=x^{1/x}}$. Therefore, when it is well defined, ${\displaystyle {\sqrt[{\infty }]{x}}_{s}=x^{1/x}}$ and, unlike normal tetration, is an elementary function. For example, ${\displaystyle {\sqrt[{\infty }]{2}}_{s}=2^{1/2}={\sqrt {2}}}$.

It follows from the Gelfond–Schneider theorem that super-root ${\displaystyle {\sqrt {n}}_{s}}$ for any positive integer n is either integer or transcendental, and ${\displaystyle {\sqrt[{3}]{n}}_{s}}$ is either integer or irrational.[18] It is still an open question whether irrational super-roots are transcendental in the latter case.

### Super-logarithm

Once a continuous increasing (in x) definition of tetration, xa, is selected, the corresponding super-logarithm ${\displaystyle {\text{slog}}_{a}x}$ or ${\displaystyle {\text{log}}_{a}^{4}x}$ is defined for all real numbers x, and a > 1.

The function sloga x satisfies:

${\displaystyle {\begin{array}{lcl}\operatorname {slog} _{a}{^{x}a}&=&x\\\operatorname {slog} _{a}a^{x}&=&1+\operatorname {slog} _{a}x\\\operatorname {slog} _{a}x&=&1+\operatorname {slog} _{a}\log _{a}x\\\operatorname {slog} _{a}x&>&-2\end{array}}}$

## Open questions

Other than the problems with the extensions of tetration, there are several open questions concerning tetration, particularly when concerning the relations between number systems such as integers and irrational numbers:

• It is not known whether there is a positive integer n for which nπ or ne is an integer. In particular, it is not known whether 4π is an integer.
• It is not known whether nq is an integer for any positive integer n and positive non-integer rational q.[18] Particularly, it is not known whether the positive root of the equation 4x = 2 is a rational number.

## References

1. ^ R. L. Goodstein (1947). "Transfinite ordinals in recursive number theory". Journal of Symbolic Logic. 12 (4): 123–129. doi:10.2307/2266486. JSTOR 2266486.
2. ^ N. Bromer (1987). "Superexponentiation". Mathematics Magazine. 60 (3): 169–174. JSTOR 2689566.
3. ^ J. F. MacDonnell (1989). "Somecritical points of the hyperpower function ${\displaystyle x^{x^{\dots }}}$". International Journal of Mathematical Education. 20 (2): 297–305. doi:10.1080/0020739890200210. MR 0994348.
4. ^
5. ^ a b M. H. Hooshmand, (2006). "Ultra power and ultra exponential functions". Integral Transforms and Special Functions. 17 (8): 549–558. doi:10.1080/10652460500422247.
6. ^ "Power Verb". J Vocabulary. J Software. Retrieved 28 October 2011.
7. ^ Alexander Meiburg. (2014). Analytic Extension of Tetration Through the Product Power-Tower Retrieved November 29, 2018
8. ^ a b c Müller, M. "Reihenalgebra: What comes beyond exponentiation?" (PDF). Retrieved 12 December 2018.
9. ^ "Climbing the ladder of hyper operators: tetration". George Daccache. January 5, 2015. Retrieved 18 February 2016.
10. ^ Euler, L. "De serie Lambertina Plurimisque eius insignibus proprietatibus." Acta Acad. Scient. Petropol. 2, 29–51, 1783. Reprinted in Euler, L. Opera Omnia, Series Prima, Vol. 6: Commentationes Algebraicae. Leipzig, Germany: Teubner, pp. 350–369, 1921. (facsimile)
11. ^ Trappmann, Henryk; Kouznetsov, Dmitrii (June 28, 2010). "5+ methods for real analytic tetration" (PDF). Retrieved 5 December 2018.
12. ^ a b Neyrinck, Mark. An Investigation of Arithmetic Operations. Retrieved 9 January 2019.
13. ^ Andrew Robbins. Solving for the Analytic Piecewise Extension of Tetration and the Super-logarithm. The extensions are found in part two of the paper, "Beginning of Results".
14. ^ W. Paulsen and S. Cowgill (March 2017). "Solving ${\displaystyle F(z+1)=b^{F(z)}}$ in the complex plane" (PDF). Advances in Computational Mathematics. 43: 1–22. doi:10.1007/s10444-017-9524-1.
15. ^ D. Kouznetsov (July 2009). "Solution of ${\displaystyle F(z+1)=\exp(F(z))}$ in complex ${\displaystyle z}$-plane" (PDF). Mathematics of Computation. 78 (267): 1647–1670. doi:10.1090/S0025-5718-09-02188-7.
16. ^ a b Corless, R. M.; Gonnet, G. H.; Hare, D. E. G.; Jeffrey, D. J.; Knuth, D. E. (1996). "On the Lambert W function" . Advances in Computational Mathematics. 5: 333. arXiv:1809.07369. doi:10.1007/BF02124750.
17. ^ Krishnam R. (2004), "Efficient Self-Organization Of Large Wireless Sensor Networks" - Dissertation, BOSTON UNIVERSITY, COLLEGE OF ENGINEERING. pp.37-40
18. ^ a b Marshall, Ash J., and Tan, Yiren, "A rational number of the form aa with a irrational", Mathematical Gazette 96, March 2012, pp. 106-109.
Double exponential function

A double exponential function is a constant raised to the power of an exponential function. The general formula is ${\displaystyle f(x)=a^{b^{x}}=a^{(b^{x})}}$, which grows much more quickly than an exponential function. For example, if a = b = 10:

Factorials grow more quickly than exponential functions, but much more slowly than doubly exponential functions. However, tetration and the Ackermann function grow faster. See Big O notation for a comparison of the rate of growth of various functions.

The inverse of the double exponential function is the double logarithm ln(ln(x)).

ELEMENTARY

In computational complexity theory, the complexity class ELEMENTARY of elementary recursive functions is the union of the classes

{\displaystyle {\begin{aligned}{\mathsf {ELEMENTARY}}&={\mathsf {EXP}}\cup {\mathsf {2EXP}}\cup {\mathsf {3EXP}}\cup \cdots \\&={\mathsf {DTIME}}(2^{n})\cup {\mathsf {DTIME}}(2^{2^{n}})\cup {\mathsf {DTIME}}(2^{2^{2^{n}}})\cup \cdots \end{aligned}}}

The name was coined by László Kalmár, in the context of recursive functions and undecidability; most problems in it are far from elementary. Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY. Most notably, there are primitive recursive problems that are not in ELEMENTARY. We know

LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R

Whereas ELEMENTARY contains bounded applications of exponentiation (for example, ${\displaystyle O(2^{2^{n}})}$), PR allows more general hyper operators (for example, tetration) which are not contained in ELEMENTARY.

Exponential factorial

The exponential factorial of a positive integer n, denoted by n\$, is n raised to the power of n − 1, which in turn is raised to the power of n − 2, and so on and so forth, that is,

${\displaystyle n\=n^{(n-1)^{(n-2)\cdots }}}$

The exponential factorial can also be defined with the recurrence relation

${\displaystyle a_{0}=1,\quad a_{n}=n^{a_{n-1}}}$

The first few exponential factorials are 1, 1, 2, 9, 262144, etc. (sequence A049384 in the OEIS). So, for example, 262144 is an exponential factorial since

${\displaystyle 262144=4^{3^{2^{1}}}}$

The exponential factorials grow much more quickly than regular factorials or even hyperfactorials. The exponential factorial of 5 is 5262144 which is approximately 6.206069878660874 × 10183230.

The sum of the reciprocals of the exponential factorials from 1 onwards is the transcendental number

${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{n\}}={\frac {1}{1}}+{\frac {1}{2^{1}}}+{\frac {1}{3^{2^{1}}}}+{\frac {1}{4^{3^{2^{1}}}}}+{\frac {1}{5^{4^{3^{2^{1}}}}}}+{\frac {1}{6^{5^{4^{3^{2^{1}}}}}}}+\ldots =1.611114925808376736\underbrace {11111111\ldots 11111111} _{183213}272243682859\ldots }$

This sum is transcendental because it is a Liouville number.

Like tetration, there is currently no accepted method of extension of the exponential factorial function to real and complex values of its argument, unlike the factorial function, for which such an extension is provided by the gamma function.

Googolplex

A googolplex is the number 10googol, or equivalently, 10(10100). Written out in ordinary decimal notation, it is 1 followed by 10100 zeroes, that is, a 1 followed by a googol zeroes.

Hereditarily finite set

In mathematics and set theory, hereditarily finite sets are defined as finite sets whose elements are all hereditarily finite sets.

Hyperoperation

In mathematics, the hyperoperation sequence is an infinite sequence of arithmetic operations (called hyperoperations in this context) that starts with a unary operation (the successor function with n = 0). The sequence continues with the binary operations of addition (n = 1), multiplication (n = 2), and exponentiation (n = 3).

After that, the sequence proceeds with further binary operations extending beyond exponentiation, using right-associativity. For the operations beyond exponentiation, the nth member of this sequence is named by Reuben Goodstein after the Greek prefix of n suffixed with -ation (such as tetration (n = 4), pentation (n = 5), hexation (n = 6), etc.) and can be written as using n − 2 arrows in Knuth's up-arrow notation. Each hyperoperation may be understood recursively in terms of the previous one by:

${\displaystyle a[n]b=\underbrace {a[n-1](a[n-1](a[n-1](\cdots [n-1](a[n-1](a[n-1]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a},\quad n\geq 2}$

It may also be defined according to the recursion rule part of the definition, as in Knuth's up-arrow version of the Ackermann function:

${\displaystyle a[n]b=a[n-1]\left(a[n]\left(b-1\right)\right),\quad n\geq 1}$

This can be used to easily show numbers much larger than those which scientific notation can, such as Skewes' number and googolplexplex (e.g. ${\displaystyle 50[50]50}$ is much larger than Skewes’ number and googolplexplex), but there are some numbers which even they cannot easily show, such as Graham's number and TREE(3).

This recursion rule is common to many variants of hyperoperations (see below in definition).

Iterated function

In mathematics, an iterated function is a function X → X (that is, a function from some set X to itself) which is obtained by composing another function f : X → X with itself a certain number of times. The process of repeatedly applying the same function is called iteration. In this process, starting from some initial number, the result of applying a given function is fed again in the function as input, and this process is repeated.

Iterated functions are objects of study in computer science, fractals, dynamical systems, mathematics and renormalization group physics.

Iterated logarithm

In computer science, the iterated logarithm of ${\displaystyle n}$, written log* ${\displaystyle n}$ (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to ${\displaystyle 1}$. The simplest formal definition is the result of this recurrence relation:

${\displaystyle \log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}}$

On the positive real numbers, the continuous super-logarithm (inverse tetration) is essentially equivalent:

${\displaystyle \log ^{*}n=\lceil \mathrm {slog} _{e}(n)\rceil }$

but on the negative real numbers, log-star is ${\displaystyle 0}$, whereas ${\displaystyle \lceil {\text{slog}}_{e}(-x)\rceil =-1}$ for positive ${\displaystyle x}$, so the two functions differ for negative arguments.

The iterated logarithm accepts any positive real number and yields an integer. Graphically, it can be understood as the number of "zig-zags" needed in Figure 1 to reach the interval ${\displaystyle [0,1]}$ on the x-axis.

In computer science, lg* is often used to indicate the binary iterated logarithm, which iterates the binary logarithm (with base ${\displaystyle 2}$) instead of the natural logarithm (with base e).

Mathematically, the iterated logarithm is well-defined for any base greater than ${\displaystyle 1}$, not only for base ${\displaystyle 2}$ and base e.

Knuth's up-arrow notation

In mathematics, Knuth's up-arrow notation is a method of notation for very large integers, introduced by Donald Knuth in 1976. It is closely related to the Ackermann function and especially to the hyperoperation sequence. The idea is based on the fact that multiplication can be viewed as iterated addition and exponentiation as iterated multiplication. Continuing in this manner leads to tetration (iterated exponentiation) and to the remainder of the hyperoperation sequence, which is commonly denoted using Knuth arrow notation. This notation allows for a simple description of numbers far larger than can be explicitly written out.

A single arrow means exponentiation (iterated multiplication); more than one arrow means iterating the operation associated with one fewer arrow.

For example:

${\displaystyle 2\uparrow 4=2\times (2\times (2\times 2))=2^{4}=16}$
${\displaystyle 2\uparrow \uparrow 4=2\uparrow (2\uparrow (2\uparrow 2))=2^{2^{2^{2}}}=65536}$
{\displaystyle {\begin{aligned}2\uparrow \uparrow \uparrow 3&=2\uparrow \uparrow (2\uparrow \uparrow 2)\\&=2\uparrow \uparrow (2\uparrow 2)\\&=2\uparrow \uparrow 4\\\end{aligned}}}

The general definition of the notation (by recursion) is as follows (for integer a and non-negative integers b and n):

${\displaystyle a\uparrow ^{n}b={\begin{cases}a^{b},&{\text{if }}n=1;\\1,&{\text{if }}n\geq 1{\text{ and }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\text{otherwise }}\end{cases}}}$

Here, ↑n stands for n arrows, so for example

${\displaystyle 2\uparrow \uparrow \uparrow \uparrow 3=2\uparrow ^{4}3}$.
Large numbers

Large numbers are numbers that are significantly larger than those ordinarily used in everyday life, for instance in simple counting or in monetary transactions. The term typically refers to large positive integers, or more generally, large positive real numbers, but it may also be used in other contexts.

Very large numbers often occur in fields such as mathematics, cosmology, cryptography, and statistical mechanics. Sometimes people refer to numbers as being "astronomically large". However, it is easy to mathematically define numbers that are much larger even than those used in astronomy.

List of exponential topics

Accelerating change

Approximating natural exponents (log base e)

Artin–Hasse exponential

Bacterial growth

Baker–Campbell–Hausdorff formula

Cell growth

Barometric formula

Beer–Lambert law

Characterizations of the exponential function

Catenary

Compound interest

De Moivre's formula

Derivative of the exponential map

Doubling time

e-folding

Elimination half-life

Error exponent

Euler's formula

Euler's identity

e (mathematical constant)

Exponent

Exponent bias

Exponential (disambiguation)

Exponential backoff

Exponential decay

Exponential dichotomy

Exponential discounting

Exponential diophantine equation

Exponential dispersion model

Exponential distribution

Exponential error

Exponential factorial

Exponential family

Exponential field

Exponential formula

Exponential function

Exponential generating function

Exponential-Golomb coding

Exponential growth

Exponential hierarchy

Exponential integral

Exponential integrator

Exponential map (Lie theory)

Exponential map (Riemannian geometry)

Exponential notation

Exponential object (category theory)

Exponential response formula

Exponential sheaf sequence

Exponential smoothing

Exponential stability

Exponential sum

Exponential time

Sub-exponential time

Exponential tree

Exponential type

Exponentially equivalent measures

Exponentiating by squaring

Exponentiation

Fermat's Last Theorem

Forgetting curve

Gaussian function

Gudermannian function

Half-exponential function

Half-life

Hyperbolic function

Inflation, inflation rate

Interest

Limiting factor

Lindemann–Weierstrass theorem

List of integrals of exponential functions

List of integrals of hyperbolic functions

Lyapunov exponent

Malthusian catastrophe

Malthusian growth model

Marshall–Olkin exponential distribution

Matrix exponential

Moore's law

Nachbin's theorem

Piano key frequencies

Power law

Proof that e is irrational

Proof that e is transcendental

Q-exponential

Rule of 70, Rule of 72

Scientific notation

Six exponentials theorem

Spontaneous emission

Super-exponentiation

Tetration

Versor

Wilkie's theorem

Zenzizenzizenzic

PR (complexity)

PR is the complexity class of all primitive recursive functions—or, equivalently, the set of all formal languages that can be decided by such a function. This includes addition, multiplication, exponentiation, tetration, etc.

The Ackermann function is an example of a function that is not primitive recursive, showing that PR is strictly contained in R (Cooper 2004:88).

On the other hand, we can "enumerate" any recursively enumerable set (see also its complexity class RE) by a primitive-recursive function in the following sense: given an input (M, k), where M is a Turing machine and k is an integer, if M halts within k steps then output M; otherwise output nothing. Then the union of the outputs, over all possible inputs (M, k), is exactly the set of M that halt.

PR strictly contains ELEMENTARY.

PR does not contain "PR-complete" problems (assuming, e.g., reductions that belong to ELEMENTARY). In practice, many problems that are not in PR but just beyond are ${\displaystyle {\text{𝐅}}_{\omega }}$-complete (Schmitz 2016).

Pentation

In mathematics, pentation is the next hyperoperation after tetration but before hexation. It is defined as iterated (repeated) tetration, just as tetration is iterated exponentiation. It is a binary operation defined with two numbers a and b, where a is tetrated to itself b times. For instance, using hyperoperation notation for pentation and tetration, ${\displaystyle 2[5]3}$ means tetrating 2 to itself 3 times, or ${\displaystyle 2[4](2[4]2)}$. This can then be reduced to ${\displaystyle 2[4](2^{2})=2[4]4=2^{2^{2^{2}}}=2^{2^{4}}=2^{16}=65536.}$

Power tower

Power tower may refer to:

Power Tower, a thrill ride at Valleyfair and Cedar Point amusement parks in the USA

Power tower (power take-off), a type of mechanical power take-off (PTO)

Solar power tower, a type of solar power plant

Tetration, a mathematical operation also known as power tower, hyperpower, or superexponentiation

Transmission tower, usually a tall steel lattice tower supporting an overhead electric power line (aka electricity pylon, hydro tower, etc.)

Power tower (exercise), equipment can include pull up handles, dip bars, push up grips and captain's chair forearm pads

Power tower (Linz), an office building in Linz, Austria

Successor function

In mathematics, the successor function or successor operation is a primitive recursive function S such that S(n) = n+1 for each natural number n.

For example, S(1) = 2 and S(2) = 3. Successor operations are also known as zeration in the context of a zeroth hyperoperation: H0(a, b) = 1 + b. In this context, the extension of zeration is addition, which is defined as repeated succession.

Super-logarithm

In mathematics, the super-logarithm is one of the two inverse functions of tetration. Just as exponentiation has two inverse functions, roots and logarithms, tetration has two inverse functions, super-roots and super-logarithms. There are several ways of interpreting super-logarithms:

For positive integer values, the super-logarithm with base-e is equivalent to the number of times a logarithm must be iterated to get to 1 (the Iterated logarithm). However, this is not true for negative values and so cannot be considered a full definition. The precise definition of the super-logarithm depends on a precise definition of non-integral tetration (that is, ${\displaystyle {^{y}x}}$ for y not an integer). There is no clear consensus on the definition of non-integral tetration and so there is likewise no clear consensus on the super-logarithm for non-integer range.

Superfunction

In mathematics, superfunction is a nonstandard name for an iterated function for complexified continuous iteration index. Roughly, for some function f and for some variable x, the superfunction could be defined by the expression

${\displaystyle S(z;x)=\underbrace {f{\Big (}f{\big (}\dots f(x)\dots {\big )}{\Big )}} _{z{\text{ evaluations of the function }}f}.}$

Then, S(z;x) can be interpreted as the superfunction of the function f(x). Such a definition is valid only for a positive integer index z. The variable x is often omitted. Much study and many applications of superfunctions employ various extensions of these superfunctions to complex and continuous indices; and the analysis of the existence, uniqueness and their evaluation. The Ackermann functions and tetration can be interpreted in terms of super-functions.

Superpower (disambiguation)

Superpower, a state with the ability to influence events and project power on a worldwide scale

Second Superpower, a term used to conceptualize a global civil society as a counterpoint to the United States of America

Energy superpower

Potential superpowersSuperpower may also refer to:

Superpower (ability), extraordinary powers mostly possessed by fictional characters, commonly in American comic books

Tetration, superpower or hyperpower is used as synonym of tetration.

^^

^^ may refer to:

A kaomoji

Tetration, the ASCII form of the tetration operator

Record separator, control character in the caret notation

Logical exclusive or, operator in the GLSL language

Primary
Inverse for left argument
Inverse for right argument
Related articles
Examples in
numerical order
Expression
methods
Related
articles
(alphabetical order)

This page is based on a Wikipedia article written by authors (here).
Text is available under the CC BY-SA 3.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.