Bruno writes: > Meanwhile just a few questions to help me. They are hints for the=20 > problem too. Are you familiar with the following "recursive" program=20 > for computing the factorial function? > > fact(0) =3D 1 > fact (n) =3D n * fact(n - 1) > > Could you compute "fact 5", from that program? Could you find a similar=20 > recursive definition (program) for multiplication (assuming your=20 > machine already know how to add)? > Could you define exponentiation from multiplication in a similar way? =20 > Could you find a function which would grow more quickly than=20 > exponentiation and which would be defined from exponentiation like=20 > exponentiation is defined from multiplication? Could you generalize all=20 > this and define a sequence of more and more growing functions. Could=20 > you then diagonalise effectively (=3D writing a program who does the=20 > diagonalization) that sequence of growing functions so as to get a=20 > function which grows more quickly than any such one in the preceding=20 > sequence?
Here's what I think you are getting at with the fairy problem. The point is not to write down the last natural number, because of course there is no such number. Rather, you want to write a program which represents (i.e. would compute) some specific large number, and you want to come up with the best program you can for this, i.e. the program that produces the largest number from among all the programs you can think of. If we start with factorial, we could define a function func0 as: func0(n) = fact(n) Now this gets big pretty fast. func0(100) is already enormous, it's like a 150 digit number. However we can "stack" this function by calling it on itself. func0(func0(100)) is beyond comprehension. And we can generalize, to call it on itself as many times as we want, like n times: func1(n) = func0(func0(func0( ... (n))) ... ))) where we have nested calls of func0 on itself n times. This really gets bigger fast, much faster than func0. Then we can nest func1: func2(n) = func1(func1(func1( ... (n))) ... ))) where again we have nested calls of func1 on itself n times. We know that func1(n) gets bigger so fast, func1(func1(n)) will get bigger amazingly faster, and of course with n of them it is that much faster yet. This clearly generalizes to func3, func4, .... Now we can step up a level and define hfunc1(n) = funcn(n), the nth function along the path from func1, func2, func3, .... Wow, imagine how fast that gets bigger. hfunc is for "hyperfunc". Then we can stack the hfuncs, and go to an ifunc, a jfunc, etc. Well, my terminology is getting in the way since I used letters instead of numbers here. But if I were more careful I think it would be possible to continue this process more or less indefinitely. You'd have program P1 which continues this process of stacking and generalizing, stacking and generalizing. Then you could define program P2 which runs P1 through n stack-and-generalize sequences. Then we stack-and-generalize P2, etc. It never ends. But it's not clear to me how to describe the process formally. So we have this ongoing process where we define a series of functions that get big faster and faster than the ones before. I'm not sure how we use it. Maybe at some point we just tell the fairy, okay, let me live P1000(1000) years. That's a number so big that from our perspective it seems like it's practically infinite. But of course from the infinite perspective it seems like it's practically zero. Hal Finney --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to email@example.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~----------~----~----~----~------~----~------~--~---