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
(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  3 = 7,
4  3 = 12,
4  3 = 64,
4  3 =
4  4 = 4 ^ <the preceding number> [out-of-range of most computer
without additional work!]
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  x,
F5(x) = x  x, F6(x) = x  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
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.
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.
0) Could you evaluate roughly the number of digit of 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 ...
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To post to this group, send email to firstname.lastname@example.org
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at