Hi George, Tom, Hal, and others, OK. I hope it is clear for everybody that, exactly like we have a natural infinite sequence of positive integer or natural numbers:
0, 1, 2, 3, 4, etc. We have a natural sequence of growing functions, (also called operations): ADDITION MULTIPLICATION EXPONENTIATION TETRATION PENTATION HEXATION HEPTATION OCTATION ENNEATION DECATION 11-ATION 12-ATION TRISKAIDEKATION 14-ATION 15-ATION 16-ATION 17-ATION ... (I remember the greek name of 13 thanks to the disease "triskadekaphobia" : the fear of the number 13 :) We can use the notation [n] for any n-ation, so that for example: 4 [1] 3 = 7, 4 [2] 3 = 12, 4 [3] 3 = 64, 4 [4] 3 = 134078079299425970995740249982058461274793658205923933777235614437217640 300735469768018742981669034276900318581864860508537538828119465699464336 49006084096, 4 [4] 4 = 4 ^ <the preceding number> [out-of-range of most computer without additional work!] etc. Let us write Fi(x) = x [i] x ; Indeed it will be more easy to illustrate diagonalization on one variable function: Thus F1(x) = x + x; F2(x) = x * x, F3(x) = x ^ x, F4(x) = x [4] x, F5(x) = x [5] x, F6(x) = x [6] x, etc. This gives us an infinite list of one variable growing functions F0 F1, F2, F3, F4, F5, F6, F7, ... Please note that I could have taken Hal Finney list, H0 H1 H2 H3 H4 H5 H6 H7 H8 H9 ...where H0(x) = factorial(x), H1(x) = factorial(factorial 2), H2(x) = factorial(factorial (factorial (x))), ... Mmmh... I am realizing it will even be easier to diagonalize transfinitely with Hal Finney's functions than with the traditional one, because with Hal Finney's one we will not been obliged of doing some back and forth between one and two variable functions. Anyway, let F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 ... be your favorite sequence of one-variable more and more growing function. (I recall all function here are function defined on N and with value in N; where N = the set of natural numbers : 0, 1, 2, 3, ... Here is a growing function, build from that class from diagonalization: g(x) = Fx(x) + 1 (in english: to compute g(x), search the xth function in your sequence, and apply it to x and then add 1. For example g(3) = F3(3) + 1, g(245) = F245(245) + 1, etc. 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/ --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
