I've been toying around with figuring out what comes after
exponentiation. I've come up with a simplistic (meaning it works but
not efficiently) way of calculating those values for integers >= 1,
but I'd like to also figure out how to do real numbers as well as
negative numbers. Furthermore, I'd actually like to be able to
calculate these values for x and y where x and y are not tiny numbers.
I've found that my code slows to a craw for small x,y values like
g(3,4,10). That's not surprising considering that g(3,4,9) is a 39457
digit base 10 number, but still...

First, here's what I've come up with.

g(a,x,y) is a function which gives the result of the operation denoted by "a".
a is an integer >= 0
x is an integer > 0
y is an integer > 0
g(0,x,y) = x + y
g(1,x,y) = x * y
g(2,x,y) = x ^ y

To calculate the result of g(a,x,y):
g(0,x,y) = x + y
g(a,x,1) = x    [a > 0]
g(a,x,y) = g(a-1, x, g(a,x,y-1) )    [a>0, x>0, y>1]

Things I've proven based on the above axioms:
g(a,x,y) = g( a-1, g(a,x,y-1), x )    [a>0, x>0, y>1]
g(a+1,x,2) = g(a,x,x)
g(a,1,y) = 1    [a>=2]


I'd like to be able to use real numbers for x and y. Once I get that
then I can figure out what comes next in the sequence: subtraction,
division, taking the root

I'd like to be able to have negative numbers for x and y, although
negative numbers aren't allowed as exponents, so I guess maybe y would
have to be required to be positive for a=2. I don't know, but it may
need to be positive for a>=2. I haven't proven that yet.

g(a,x,y) = g(a,y,x)    [a>=0, a<=1]
In other words, addition and multiplication are commutative. I know
that a=2 (exponentiation) is not commutative, but I'd like to prove
whether or not that is the case for a>2.

I have to keep y>0 because
g(0,x,0) = x
g(1,x,0) = 0
g(2,x,0) = 1
I have no idea what g(a,x,0) would/should be for a>2.

If anyone is interested I can post the source code and the proofs, but
it's probably not useful until I get a more complete algorithm that
includes the things I mentioned above.

Hi mxnmatch-ga,

The operation after addition, multiplication and exponentiation is
known variously as hyper exponentiation, tetration or power tower.
Although many aspects of tetration have been studied since ###'s time,
it is still a fertile field of mathematical research.

NOTATION

A wide variety of notation is used for tetration and other hyper
operators. What you have defined as g(3, x, y) is also notated as:

   hyper4(x, y)
   hyper(x, 4, y)
   x ^ ^ y  (Knuth's up-arrow notation)
   x -> y -> 2  (Conway's notation)

See:

   Hyper operator (Wikipedia)
   http://en.wikipedia.org/wiki/Hyper_operator

   Knuth's up-arrow notation (Wikipedia)
   http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation

   Conway chained arrow notation (Wikipedia)
   http://en.wikipedia.org/wiki/Conway_chained_arrow_notation

EXTENSION TO LOW VALUES OF 'y'

By using a logarithmic representation of the definition of tetration,
one can derive the following:

   g(3,x,1) = x
   g(3,x,0) = 1
   g(3,x,-1) = 0 (except undefined for x = 1)

We can also derive these:

   g(3,0,y) = 1 (when 'y' is an even integer)
   g(3,0,y) = 0 (when 'y' is an odd integer)

If you define 0^0 (zero to the zeroth power) to equal one, these
values hold exactly. If you take 0^0 to be undefined, these values are
approached as x approaches zero (from the positive or negative
direction).

I can't easily type the mathematic notation for this and other
derivations in ASCII, but see:

   Tetration (Wikipedia)
   http://en.wikipedia.org/wiki/Tetration

COMMUTATIVITY

I think it is safe to say that since g(2,x,y) is non-commutative, and
since g(3,x,y) and higher are defined recursively in terms of
g(2,x,y), that g(3,x,y) and higher are also non-commutative.

EXTENSION BEYOND INTEGERS

Tetration can be extended to real number values of 'x':

   Tetration - Extension to real numbers
   http://en.wikipedia.org/wiki/Tetration#Extension_to_real_numbers

Here's a most attractive graph showing g(3, x, y) for real 'x' and for
y=2,3,4,5,6,7:

   http://upload.wikimedia.org/wikipedia/en/6/68/Tetration_large.png

The extension of tetration for real 'y' is a subject of active research:

   Extension of the hyper4 function to reals
   http://home.earthlink.net/~mrob/pub/math/ln-notes1.html#real-hyper4

   A Continuous Extension For the Hyper4 Operator
   http://ioannis.virtualcomposer2000.com/math/exponents4.html

Tetration can also be extended to complex number values of 'x':

   Complex tetration
   http://en.wikipedia.org/wiki/Tetration#Complex_tetration

We can also reason about tetration with infinite 'y'. For example,
g(3, root-2, infinity) equals 2.

   Infinite Exponentials
   http://ioannis.virtualcomposer2000.com/math/exponents.html

EXTENSION IN THE OTHER DIRECTION

Remarkably, g(-1,x,y) can be given a meaning too:

  "This new operation [with a heirarchical level less than
   that of addition] has been called ?zeration?. The inverse
   operation of zeration (commutative) generates a new class
   of numbers (the Rubtsov?s ?delta? numbers) that can be
   put in bi-jection with the set of the logarithms of
   negative numbers."

   Hyper-operations
  http://forum.wolframscience.com/showthread.php?s=6e82a32b800c7293c9647a6c50598ffa&postid=1846#post1846

CALCULATING g(a, x, y)

As you have observed, calculation of g(3,x,y) is slow. That's because
it involves deep and repeated recursion. There are three approaches
that can be taken:

The first approach is to ptimise the recursion. Here we can exploit
the work done in optimising Ackermann's function, which is closely
related to your function 'g'. In fact, Ackermann's original function
A(m,n,p) directly corresponds to g(p+1,m,n). However, Ackermann's
function is more often encountered in a two-argument form defined as
follows:

   A(m,n) = n+1             if m=0
   A(m,n) = A(m-1,1)        if m>0 and n=0
   A(m,n) = A(m-1,A(m,n-1)) if m>0 and n>0

You will see some similarities between this and your own recursive
definition of g(a,x,y). Indeed, A(m,n) = g(m-1,2,n+3)?3.

To speed up this kind of calculation, it is necessary to cache some of
the intermediate values so that they are not repeated recalculated. In
addition, identities such as A(3,n)=8×2^n?3 can be used to make the
recursion much shallower.

See:

   Ackermann Function (Wikipedia)
   http://en.wikipedia.org/wiki/Ackermann_function

particularly the sections on "Use as benchmark" and "table of values", and also:

   Ackermann Function (from Wolfram MathWorld)
   http://mathworld.wolfram.com/AckermannFunction.html

   Analytic Continuation of the Ackermann Function
   (What lies beyond exponentiation?)
   http://tetration.samaj.us/ssu/index_files/v3_document.htm

Compilers and interpreters for some programming languages can
automatically calculate and cache internal values, which can make an
enormous difference to the running time of an unoptimised program. You
can see from the following benchmark results that different languages
have a range of more than 500:1 in execution time for calculating
A(3,x). You may therefore wish to use a programming language that
appears near the top of the list for your own calculations.

   Recursive benchmark - computer language shootout benchmarks
   http://shootout.alioth.debian.org/gp4/benchmark.php?test=recursive&lang=all

The second approach to computing g(3,x,y) is to use a maths
application. A package such as Mathematica is likely to perform
advanced optimizations that will greatly speed up computation time.

Here's an implementation for Mathematica:

   Power Tower - from Wolfram MathWorld
   http://mathworld.wolfram.com/PowerTower.html

together with a bunch of tables, graphs and references.

The third approach is to use a series expansion. One is derived here:

   A series expansion for (e^x)^(e^x)^(e^x)...
   http://ioannis.virtualcomposer2000.com/math/exponents5.html

It looks like considerable work would be required to turn this into a
practical application, although some code is provided for the Maple
maths package.

FURTHER STUDY

For a large collection of related research, see:

   A Collection of References Related to Infinite Exponentials and Tetration
   http://ioannis.virtualcomposer2000.com/math/IERefs.html

I trust this answer, and the links provided, address the points you
raised in your question. If not, feel free to request clarification.

Regards,
eiffel-ga


Google Search Strategy:

hyper exponentiation
://www.google.com/search?q=hyper+exponentiation

ackermann's function
://www.google.com/search?q=ackermann%27s+function


Additional Links:

Mathematics Articles by I N Galidakis (including hyper exponentiation)
http://ioannis.virtualcomposer2000.com/math/index.html

---

Clarification of Answer by eiffel-ga on 04 Jul 2006 06:19 PDT

Two small corrections:

The phrase "studied since ###'s time" should read "studied since
Euler's time", and the word "ptimise" should be "optimise".

That's exactly what I needed! Thanks!

I was particularly interested in the concept of zeration, but a quick
search didn't turn much up on it. And, since there's a wikipedia
discussion that pretty much dismisses it, I guess it also is an area
that hasn't been delved into much yet.

I've asked a related question here in case you'd like to answer that one.
http://answers.google.com/answers/threadview?id=743424

Many years ago I took a graduate math class from the famous Alfred
Tarski in which he defined "+ sub alpha" for every ordinal alpha. When
alpha is 0, 1, 2 we get respectively +, *, ^ . The next one is
hyperexponentiation, then hyperhyperexponentiation, etc. The main step
is obtained from generalizing a^(b+1) = (a^b) * a and becomes a (+ sub
alpha+1) (b+1) = [a (+ sub alpha+1) b] (+ sub alpha) a. These are
defined for all ordinals (and can be restricted to positive integers
if you wish).

Note that no (+ sub alpha) for alpha>2 is commutative and that for all
ordinals alpha

 2 (+ sub alpha) 2 = 4. 

Also at limit ordinals one just takes unions. I'm sure for finite
alpha one can extend these definitions to positive reals.

This has got to be one of the best question and answers I have seen
here. I wonder what kinds of applications this has in engineering or
physics. However, can't these operations like tetration always be
written in terms of the old *,+ etc? If so, I don't see the point of
doing this?

Hi saem_aero-ga, I'm glad you enjoyed this question and answer.

The operation of multiplication can always be written using repeated
addition, yet we still find it useful to have a specific notation for
multiplication. Similarly, we can reason about tetration more easily
if we have a high-level notation for it.

Like much of pure mathemetics, the "point of doing this" is not always
immediately obvious. However, future applications may emerge. For
example, G F Romerio has suggested that instead of computers
overflowing when a number is too big, they instead have a soft failure
into a "tetration order of magnitude" which would give an idea of just
how much "too big" the number is. He has also suggested that "the new
zeration operation can be used to systematically describe
discontinuities such those normally defined by the step or Dirac?s
function". That could surely lead to applications in electronics and
other branches of physics.

   Hyper-operations - Forum - G F Romerio
   http://forum.wolframscience.com/showthread.php?s=6e82a32b800c7293c9647a6c50598ffa&postid=1846#post1846

Regards,
eiffel-ga

Dear mxnmatch-ga!

I should like to send you a comment concerning the definition of the
?zeration? operation. As you know, initially, I wrote these comments
in Russian (original text) and I produced from it an automatic
computer translation in English. I already posted both of them for
completing and possibly supporting with the Russian original the very
bad English translation. Now, after the elimination of the previous
English text, I am posting hereafter a revised English version,
grouped in four points.

Point 1 (The name). 

Indeed, the new term ?zeration? has been proposed by my friend G. F.
Romerio in the framework of our 4-year cooperation but, until now, the
article about ?zeration? has not yet been accepted in the English
version of Wikipedia. Nevertheless, the zeration operation is
mentioned, as the operation of "???????? ???????? ??????? (n=0)" (i.e.
the null operation) or "the operation with a rank lower than addition"
(weaker than addition)in my scientific publications, in Russian, since
1987.
See: http://numbers.newmail.ru/english/01.htm
Unfortunately, all these publications are written in Russian and they
are poorly known in the English part of the Internet. In this
connection, in the Russian section of Wikipedia, an article on
?zeration? has met with the approval of the readers and it is now
accessible in Russian.
See: http://ru.wikipedia.org/wiki/Zeration.
It is necessary to observe that, since August 22, 2006, the zeration
operation (identified with this name) is present within the works of
the ICM-2006 mathematical congress (see the International Congress of
Mathematicians: Abstracts, Posters, Short Communications, Mathematical
Software, Other Activities, p. 22-23, Hyper-operations as a tool for
science and engineering).
See: http://icm2006.org/AbsDef/Posters/abs_0480.pdf.
Therefore, the Wikipedia?s claim of a lack of mention of the term
?zeration? in the English-speaking printed literature is not true.

Point 2.(Theory) 

As a matter of fact, I think that nobody else until now was ever
seriously engaged in the study of this problem. On the one hand, in
fact, there is a well established set of historical mathematical
problems and tasks, for the solution of which support and financing
are provided to researchers with top priority. On the other hand,
during 19 years of operation and study of ?zeration?, I never met any
opponent who could specify to me any error or wrong approach. The
concept provided in elementary schools strongly predominates, i.e.
that ?addition? is the basic elementary operation of Arithmetic and
Algebra. Nobody is ready to go through this strong psychological
barrier. In 1996, I published a monograph in Russian, where the
results obtained from the study of ?zeration? are explicitly
presented. Unfortunately, I don?t have an acceptable English
translation of this monograph in a machine-readable format. What
exists is only a set of English texts (of medium-low quality) taken
from separate chapters. These texts can be found in the Internet on my
WEB-page http://numbers.newnail.ru, and were obtained as computer
translations, carried out in 1998. I should like to stress that a
detailed study of zeration is still necessary. It is a very
interesting hyper-operation, it brings a lot of new concepts and it
solves some old problems.

Point 3. (Applications)

What would be the practical application of ?zeration?? Let's take into
consideration another question: What will happens if we assumed that
the real elementary operation is ?multiplication?? In this case, we
should probably introduce some very complicated algorithms for the
treatment of formulas including what nowadays we call ?addition?! At
the same time, probably, we would also be obliged to define some
higher level transcendent functions, which would contain formulas
representing the ?addition? operation. However, in defining such
functions, we would say that they cannot be analytically noted by
using AVAILABLE mathematical  operations. At this point, we might have
asked to ourselves why not to define such new operations!?! We might
also observe that research activities on ?tetration? (which has a rank
higher than exponentiation) are becoming popular, but also that nobody
ever considered any other basic operation. In particular, nobody made
any research in the field of the huge amount of hyper-operations with
ranks below addition! Apparently, from the above-mentioned abstract
point of view, ?addition? is unfortunately the accepted basic scheme
for defining all the operations of the higher ranks, used for
building-up abstract models of the physical processes. What will then
happen if zeration suddenly appeared (in the accepted schemes for
defining all the other operations)!?! On the contrary, let us imagine
which are the consequence, now, of NOT using ?zeration? in
Mathematics:
a). The need of separating composite processes into parts, which has
the consequence of applying mathematical formalisms, separately, as a
set of different equations with separate conditions.
b). The definition of different ?ad-hoc? transcendent functions, e.g.
the absolute value of a real number (|x|), max, min, the function of
sign (sgn), etc.
c). In case of conflict in a notation formalism, the compulsory
introduction of limitations and, for ?the sake of precision?, the
definition of new functional symbols. Take, for example, the
arithmetical and algebraic square root, where the relationship between
cause and effect is roughly broken and a new definition of root (of
even of powers) is introduced without an explanation of causes and
effects from established mathematical concepts! On the contrary, the
introduction of ?zeration? is well supported with basic definitions of
the necessary binary operations. This liquidates all
?misunderstandings? and, to be exact, it liberates from any subjective
reversion of mathematical formalisms. I think that this is a valid
argument that also supports the reliability of mathematical
definitions. Actually, ?zeration? would allow to analytically note
many physical processes, without the simulated input of higher
transcendent functions  etc. When looking at the world around us,
where there is a moving matter with its  interactions, it becomes
understandable that ?zeration?, most likely, could become an even more
useful operation than ?addition?! It is also possible to imagine that
?zeration? is the fundamental mathematical operation with which it
would be possible to precisely describe physical movement and
interactions, e.g. the transition of a physical substance from one
status into another. The bases of traditional Mathematics for studying
the movement of physical matter (including the theory of transport)
are based on the theory of limits and on all the mathematical
magnitudes obtained by applying this theory (via the differential and
integral calculus, etc.). But, in this way, we obtain mathematical
expressions which can only approximate (with a limited precision) the
physical process of transport. A problem of traditional Mathematics is
the lack of availability of a precise description of the transition
from discrete to continuum. The use of ?zeration? solves this problem,
since ?zeration? is the operation that provides a precise mathematical
simulation of digital processes. In association with other operations
it would also allow deriving precise mathematical expressions of
overlapping discrete and continuous processes. For this reason
?zeration? appears as an indispensable mathematical operation, within
the set of the other algebraic (arithmetical) operations. Finally,
?zeration? will facilitate the simulation of ?discontinuous? surfaces
(i.e. the surfaces having an infinite number of discontinuity points
of different kinds). The world around us consists of physical systems
having, as a rule, such types of surfaces. For the traditional
Mathematics, these are exotic systems which cannot be simulated
without rough approximations.

Point 4. (Delta numbers)

In conclusion, however, I anticipate that ?zeration?, in the near
future, will not be very popular, because orthodox mathematicians will
prefer to keep silence, in order to live ? more quietly. One of
reasons of this is that ?zeration? has an inverse operation (its
official English name has not been defined yet), from which the set of
what I called the ?delta-numbers? follows. These are absolutely new
numbers, being a new branch of the logarithms of negative numbers. And
this might destroy the customary understanding of the function theory
of a complex variable.


						Madrid, 23.08.2006
						Martin, 09.09.2006
	 Konstantin Rubtsov

P.S. I thank G. F. Romerio for his revision of my computer translation