Bruno Marchal wrote:
> 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
> (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.
> 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 ...
I don't have time right now for detailed computations, but I'll give a
few quick answers and questions.
g is the same as my f(n,n,n)+1, and I already commented that f(n,m,n)
is a growing function, since f(N,m,n) is growing for fixed N. So
clearly g is growing. As I said about f(n,m,n), the degree or "-ation"
of g grows as n (or x) grows. I recognize that adding 1 to make g is
the classical diagonalization move. It makes g different from any Fi
in the sequence Fi, i=1,2,3,... And in fact, since we add 1, rather
than subtract 1, g is larger than any Fi.
I'm having a problem with accepting g, or even my original f(n,n,n), as
a function in the same sense as with a fixed degree or "-ation" of
operation. This is because the definition of the function changes
depending on the value taken in the domain of the function. Is this
However, if we just ignore this problem, throwing caution to the wind,
then the next "logical" iteration of diagonalization is to do the
"-ation" thing on g and then diagonalize. Let Gi(x) = g(x) [i] g(x),
then let h(x) = Gx(x) + 1.
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