Hi George, Tom, Hal, and others,
OK. I hope it is clear for everybody that, exactly like we have a
natural infinite sequence of positive integer or natural numbers:
0, 1, 2, 3, 4, etc.
We have a natural sequence of growing functions, (also called
operations):
ADDITION
MULTIPLICATION
EXPONENTIATION
TETRATION
PENTATION
HEXATION
HEPTATION
OCTATION
ENNEATION
DECATION
11-ATION
12-ATION
TRISKAIDEKATION
14-ATION
15-ATION
16-ATION
17-ATION
...
(I remember the greek name of 13 thanks to the disease
"triskadekaphobia" : the fear of the number 13 :)
We can use the notation [n] for any n-ation, so that for example:
4 [1] 3 = 7,
4 [2] 3 = 12,
4 [3] 3 = 64,
4 [4] 3 =
134078079299425970995740249982058461274793658205923933777235614437217640
300735469768018742981669034276900318581864860508537538828119465699464336
49006084096,
4 [4] 4 = 4 ^ <the preceding number> [out-of-range of most computer
without additional work!]
etc.
Let us write Fi(x) = x [i] x ; Indeed it will be more easy to
illustrate diagonalization on one variable function:
Thus F1(x) = x + x; F2(x) = x * x, F3(x) = x ^ x, F4(x) = x [4] x,
F5(x) = x [5] x, F6(x) = x [6] x, etc.
This gives us an infinite list of one variable growing functions F0 F1,
F2, F3, F4, F5, F6, F7, ...
Please note that I could have taken Hal Finney list, H0 H1 H2 H3 H4 H5
H6 H7 H8 H9 ...where H0(x) = factorial(x),
H1(x) = factorial(factorial 2), H2(x) = factorial(factorial (factorial
(x))), ...
Mmmh... I am realizing it will even be easier to diagonalize
transfinitely with Hal Finney's functions than with the traditional
one, because with Hal Finney's one we will not been obliged of doing
some back and forth between one and two variable functions.
Anyway, let
F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 ...
be your favorite sequence of one-variable more and more growing
function. (I recall all function here are function defined on N and
with value in N; where N = the set of natural numbers : 0, 1, 2, 3, ...
Here is a growing function, build from that class from diagonalization:
g(x) = Fx(x) + 1 (in english: to compute g(x), search the xth
function in your sequence, and apply it to x and then add 1.
For example g(3) = F3(3) + 1, g(245) = F245(245) + 1, etc.
Exercises:
0) Could you evaluate roughly the number of digit of 4 [4] 4 ? What
about the number of digit of fact(fact(fact(fact 4))))
1) is the diagonal g function a growing function? Could g belong to the
initial sequence, does g grows more quickly than any function in the
initial sequence, and in what sense precisely.
2) Could you find a function, and even a new sequence of functions more
and more growing, and growing more than the function g?
3) Do you see why it is said that g is build by diagonalization? Where
is the diagonal?
4) Is there a universal sequence of growing functions, i. e. containing
all computable growing functions?
Must already go. Sorry for this quick piece. Solution tomorrow. Hope
things are clear. Ask any elementary question (even about notation)
before missing the real start ... Any comments , critics or suggestions
are welcome ...
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---
Received on Wed May 24 2006 - 11:39:19 PDT