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
function".
>
> 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.
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 Thu May 25 2006 - 09:38:18 PDT