# Re: Smullyan Shmullyan, give me a real example

```
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
>> 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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at