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