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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---

Reply via email to