“On the shoulders of giant numbers”
http://www.iteror.org/big/book/ch2/ch2_0.html
bigΨ
bigΨ.I. Number operations
Ψ.2. Up to the Ackermann numbers
chapter 2.0, edit 0.2.9
published: 20110107
updated: 20111230
§2.0.1. Star spangled superpowers
Allahu Akbar !
God is greater
– Call to prayer, Islam
Exponentiation a^b
or raising to a power
is the operation which iterates over
multiplication.
In this chapter the double star **
rather than the arrowhead ^
functions as the exponential operator.
The hardly extendible superscript notation a^{b}
is regarded as a remnant of a past, now gone.
a**b = a*... {a#b}
= a^b
Next comes the true superpower with three stars ***
which
Goodstein
called
tetration
(tetra = 4)
counting index 1
for addition (here 0
stars).
Our three stars equals two ^^
arrowheads
in Donald Knuth's 1976
uparrow notation
– where the operand b
always counts repetitions of items
a
. And not to Ackermann's
phi recursion
– because Ackermann's own iterator b
counts the number of inbetween arrow operators instead.
a***b = a**... {a#b}
= a^^b
The insight that *
is a countable unit,
dawns with the recognition that operators *..
can be expanded at will.
Of the various names for this family of operations that have been suggested,
Nick Bromer's
superexponentiation
is most instructive.
But Bromer's term is verbally overweight,
we'll use our superpowers
instead.
In David Hilbert's
"On the infinite"
a functional (function that takes a function as an argument)
is deemed necessary to define this, while it follows immediately from
Hilbert's own formula, that an ordinary function does the trick.
Perhaps Hilbert didn't like variables of a next recursive level
n1
substituted as arguments in lower type
n
functions,
but his roundabout definition cannot hide the fact that this
follows
immediately by
=
.
 F_{0}(a,b) = ab
 F_{n1}(a,1) = I(F_{n},a,1) = a

F_{n1}(a,b1) =
I(F_{n},a,b1)
_{ } = F_{n}(a,I(F_{n},a,b))
_{ } = F_{n}(a,F_{n1}(a,b)) == F_{n}(a,..a.) {#b#}
Note that superpower star
operations aren't really built upon powers
,
because exponentiation a**b
is the 2nd true operation in the list.
The initial operation ab
of zero stars,
which is empty and naturally resolved as
addition,
forms the start at c=0 of the superpower series,
where c
counts the number of stars
and c=1 is multiplication.
From the initial superpower rule a*1 = a
the next operations *..
are recursively ==
defined,
so that every reduction train stops at a well defined initial case.
Follows the general superpower formula
providing for an arbitrary number c
of stars.
 a*^{...}1 {*#c1} = a*^{...}1 {*#c c>0} == a*1 = a
 a*^{...}11 {*#c1} = a*^{...}a {*#c} so 11*^{..}11 == 1111

a*^{...}b1 {*#c1} =
a*^{...}(a*^{...}b) {*#c *#c1}
^{ } == a*^{.. }... {*#c a#b1}
Find instructions for calculating with numbers of superpower size in the subchapter on supercalculation.
§2.0.2. Primitive recursive functions
David Hilbert
(18621943)
We'll first explain what recursion is
and what primitive recursion,^{ }
and how all superpowers a*^{..}b
can be created just by primitive recursion.
This answers to the
metamathematical
need to classify^{ }
a function according to the simplest means
with which^{ }
to generate it.
Recursion is an initial case plus an iterative function
which lets all next steps n1
follow from current step
n
.
Primitive recursion (p.r.) initially
increments
a parameter by 1
as in
F_{0}(n) = n1
.
All next steps n1
of functions F_{c1}(R,n1)
can only be defined by
substitution
of a parameter in a known p.r. function G_{c}(X)
for a previously defined step
F_{c1}(R,n)
.
The enumeration of p.r. levels is not made iterable by setting up an extra parameter
c
to expand the levels of the function family F
directly.
Therefore the primitive recursive class of functions remains
closed.
As an example we'll generate a primitive recursive
function family^{ }
Fa_{c}
which is a bit special because we start with a function index 1
where 0 is more common.^{ }
Fa
is faster than star
superpowers,
by Fa_{c}(a,0)
= a
instead of a*^{..}0 = 1
{*#c c>1}
so that for example^{ }
Fa_{2}(a,1)
= a+a×a
The
inverse unit
can signify both the negative index  = 1
and subtraction as in a
= a1.
The applied list markers are explained in
section 4.0.5.
Family Fa_{c}
could very well have used one rule
Fa_{0}(a,b) = ab
for initialization.
Then only two axioms would have sufficed to define Fa
instead,
which is one less than for superstar or arrow operations.
 Fa_{}(a,0) = 1
 Fa_{}(a,b) = Fa_{}(a,b)1 == 1... {#b1} = b1
 Fa_{c}(a,0) {c≥0} = a
 Fa_{0}(a,1) = Fa_{}(a,Fa_{0}(a,0)) = Fa_{}(a,a) = a1
 Fa_{0}(a,b) = Fa_{}(a,Fa_{0}(a,b)) == Fa_{}(a,..a.) {#b#} = ab
 Fa_{1}(a,b) = Fa_{0}(a,Fa_{1}(a,b)) == Fa_{0}(a,..a.) {#b#} = a*b1
 Fa_{2}(a,b) == Fa_{1}(a,..a.) {#b#} = (a**i)... {#b1 0_{*}}
 Fa_{c}(a,b) = Fa_{c}(a,Fa_{c}(a,b)) > a*^{...}b1 {*#c a>0 b>0 c>1}
The reason why Fa
didn't make it as a defining algorithm for superpowers
is that its properties are not so cool as those of multiplication, etc…
Because a*b = b*a
is commutative and
Fa_{1}(a1,b)
= Fa_{1}(b1,a)
is not.
And although the virtues of exponentiation are distributive,
with a minor adaptation using logarithms the powers can be
rendered commutative
with
a**(log(b)*e/log(e))
where e
is an arbitrary exponent or base.
§2.0.3. Ackermann's jump
Wilhelm Ackermann
(18961962)
Ackermann used a
primitive recursive
φ function (phi
) as a prerequisite to construct
the higher level ψ function in his 1928 article
"On Hilbert's construction of the real numbers".
The Ack_ψ
(ψ) function makes the jump
from primitive recursion into the vast unknown.
The Ack_φ
(φ) function is a
superpower
algorithm, it differs from star
operations only with respect to the initial cases for operators c>2.
After that it grows away slightly from superpowers,
though Ack_φ
never catches up with the
upstart
function family Fa_{c}
which raised its initial case earlier at
Fa_{1}(a,0) = a
 Ack_φ(a,b,0) = ab = a+b
 Ack_φ(a,0,1) = 0
 Ack_φ(a,0,2) = 1
 Ack_φ(a,0,c) {c>11} = a (Ackermann's extra axiom)
 e.g. Ack_φ(a,1,11) = a
 Ack_φ(a,b,11) = a**b = a^b
 Ack_φ(a,1,111) = a**a
 Ack_φ(a,b,111) = a***b1 = a^^(b+1)
 Ack_φ(a,b1,c1) = Ack_φ(a,Ack_φ(a,b,c1),c)
If you'd replace the 2nd and 3d rule by a single axiom
Ack_φ(a,1,c)
{0<c<3} = a
the evaluation of all expressions of Ack_φ
where b>0
will work out fine.
Compare the relative speed of the functions of superpowers from this chapter.
The three of them are relatively close, with differing values of b
,
while arrows a^^{...}b {^#c}
increase a unit 1
of c
faster than stars.
 a*^{...}b {*#c c>11} < Ack_φ(a,b,c) < Fa_{c}(a,b) {a>0 b>0}
We still owe you Ackermann's historical psifunction
which gave rise to the concept of the Ackermann numbers.
The whole Shakespearean purpose of Ackermann's Ack_ψ
function was not to be primitive recursive, which succeeded gloriously.
Yet there was no mention of any Big numbers in Ackermann's famous
article.
 Ack_ψ(a) = Ack_φ(a,a,a)

Ack_ψ(i) == { 1, 4, 3^7625597484987,
4^^(4^^(4^^(4^^5+1)+1)+1), .. } 
ψ(4) =
φ(4,4,4) =
φ(4,φ(4,3,4),3) =
φ(4,φ(4,φ(4,2,4),3),3)
= φ(4,φ(4,φ(4,φ(4,4,3),3),3),3)
where φ(a,b,3) = φ(a,..φ(a,1,3).,2) {#b#}
= φ(a,..a.,2) {#b#}
= a**... {a#b1} = a***b1 = a^^(b+1)
The complications in working out the structure of the
4th Ackermann
number seems to show that his
extra axiom
is apart from being unnecessary also relatively unnatural.
But this depends on our view of naturalness, which is tainted by
Donald Knuth's uparrow type of superpowers.
How cumbersome we may feel about defining extra axioms is not a strong argument
in this discussion, given the
leaner
physique of Fa
with its
meaner
power operation Fa_{2}
,
which is similar to the function Ack_φ(a,b,4)
and just as unwieldy if translated to an expression with stars/arrows.
Anyhow, without the extra axiom the resulting φ' function has
the same rules as the superpower stars of
bigI.
And an expression Ack_ψ'(4)
reduces to
4^^^4
= 4^^4^^4^^4
straightforwardly (in our eyes ;)
# Big function classes
Initially all of arithmetic boils down to addition and the
natural numbers of Peano's successor function
S(n)
= n1
which share the same ground level {K.0}
of complexity – the number class.
{K.0.ab}
= a+b+1
Surely appending 1
is simpler than adding b1
,
but counting from 1..
{1#ab}
is more complex than having a
in the first place.
And philosophically, who says that anything happens
in the construction of a number?
Any evaluation is essentially a series of notational reflections
on equivalent number states.
For example exponential class {K.1.1}
functions
are created by repeating class {K.1.0}
multiplications.
But in writing a*... {a#b}
for a**b
it looks like one form of complexity is exchanged for another.
All functions up to our class {K.1.1}
are called elementary functions.
The
superpowers
dwell on the level {K.1}
of
primitive recursion,
where a function {K.1.c1}
is composed of repeated substitutions (nesting)
of earlier primitive recursive functions {K.1.c}
and its subclass counter c1
enumerates an equivalent number of
star *..
{*#c2} operators.
For a long time mathematicians could see no further.
But in 1928 Wilhelm Ackermann proved a conjecture
by Hilbert
that there are recursions which increase faster
than any primitive recursive function. These are the so called
Ackermann functions {K.2.0}
which iterate over the enumeration coefficient c
of primitive recursive functions. For example the famous
Graham's number
is best expressed by an early class
{K.2.0}
function.
As iteration of repetitions assigns a subclass
{K.1.c}
to a superpower,
so can the number of subsequent Ackermann jumps
in a higher function be used to enumerate its subclass
{K.2.d}
.
In
chapter 5
we'll prove that each of the
chained arrows
advanced by John H. Conway exactly represents such an Ackermann jump,
and their first row covers the level {K.2}
of what we've dubbed
AckermannConway
functions.
Where the length of a row of chained arrows can be expressed by the value of
parameter d
in bigE
(or by the
fourth entry
in Bowers' Exploding Array Function)
this gives us a model of the subclass counter.
Evaluation of
*
and^
operatorsAn
n1
number of superstars ina*^{...}b
equalsn
arrows (or wedges) ina^^{..}b
But there are differences with respect to their order
^{ }
of evaluation or precedence in complex expressions. Given competing star operationsa*^{..}b*^{..}c
(without brackets) we evaluate the smaller operation with less stars before the larger operation. This we call minority precedence,^{ }
contrary to the common majority precedence, which applies to arrow operationsa^^{..}b^^{..}c
We let arrows take precedence above stars,
^{ }
so in expressions where both stars and arrows appear, every arrow operation is resolved first.^{ }
Types of precedence are further investigated in subchapter 2.5.