Le 24-mai-06, à 18:30, Tom Caylor a écrit :

>> 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/
> 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
> valid?

It is. Actually the definition of your f does not change, given that 
you are using a parameter to capture that change.
It is valid because you did build a well defined computable function.
Actually Ackermann invented his function for showing the existence of a 
computable function (from N to N) which does not belong to the already 
very large (but not universal) set of so called "primitive recursive 

> 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.

Good idea. And there is no reason to stop there in case the fairy give 
you some more paper. See my next post.



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 

Reply via email to