Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 (Tek) 9/28/84 based on 9/17/84; site tekchips.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxb!mhuxn!mhuxm!mhuxj!houxm!vax135!cornell!uw-beaver!tektronix!tekcrl!tekchips!abdali
From: abdali@tekchips.UUCP (Kamal Abdali)
Newsgroups: net.math
Subject: Re: Beyond Exponentiation
Message-ID: <250@tekchips.UUCP>
Date: Tue, 29-Jan-85 19:38:51 EST
Article-I.D.: tekchips.250
Posted: Tue Jan 29 19:38:51 1985
Date-Received: Thu, 31-Jan-85 01:30:20 EST
References: <186@ihnet.UUCP>
Organization: Tektronix, Beaverton OR
Lines: 38

-----------------------------
> what is the next function in the following sequence?
> Allow me to use '^' for exponentiation.
> 	y = 2
> 	y = 2*x
> 	y = 2^x
> 	???
> Each operation evolve from an iteration of the previous (originally).
> 
> ihnp4!ihnet!eklhad

Addition, multiplication, exponentiation, ... form a sequence of
operations each of which is defined in terms of repeated applications
of the previous operation.  Additional operations of the sequence
don't seem to have any standard names because they are not of much use.
In fact, I don't know of any use of these except in compuatability and
complexity theories.  Somewhere I saw the names tetration, pentation,
hexation, etc. for the successive operations after exponentiation.  The
whole family of operations is represented by the (generalized, or
original) Ackermann's function described, for example, in ``Elementary
Computability, Formal Languages, and Automata'' by R. McNaughton,
Prentice-Hall, 1982.  I like to call theses operations n-ation, with
1-ation, 2-ation, 3-ation being the same as addition, multiplication,
exponentiation, respectively.  0-ation is a special form of successor
operation.  These should formally be defined so that we will have
 
      a OP  b    =    b+2 if a=b, b+1 otherwise
          0

      a OP   b   =    a OP  (a OP  (a OP  ... (a OP  a)) ... ))
          n+1             n      n      n          n
                      -----------------------------------------
                                (b occurrences of a)

The notation G(n) is used in ``Design and Analysis of Computer
Algorithms'' by Aho, Hopcroft, and Ullman for what we may call ``4-log
base 2 of n'', i.e. G(n) = the least k such that 2 OP  k >= n.
						     4