home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17180 < prev    next >
Encoding:
Text File  |  1992-12-21  |  1.6 KB  |  59 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!stanford.edu!nntp.Stanford.EDU!ilan
  3. From: ilan@leland.Stanford.EDU (ilan vardi)
  4. Subject: Re: Large numbers
  5. Message-ID: <1992Dec18.205938.22759@leland.Stanford.EDU>
  6. Sender: news@leland.Stanford.EDU (USENET News System)
  7. Organization: DSG, Stanford University, CA 94305, USA
  8. Date: Fri, 18 Dec 92 20:59:38 GMT
  9. Lines: 48
  10.  
  11. There is a possibly interesting game consisting of trying to name
  12. larger numbers than your opponent, where the rules are that you can
  13. operate on his number and the point is that you use few operations to
  14. name a bigger number. For example:
  15.  
  16. A: names 5 
  17.  
  18. B: names 5 + 1
  19.  
  20. But B could have said 2*5 and done better, or else 2^5. So in general
  21. you would get
  22.  
  23. A: names n
  24.  
  25. B: ``I successor you,'' i.e., n+1
  26.  
  27.    ``I double you'', i.e., 2*n.
  28.  
  29.    ``I exponentiate you,'' i.e., 2^n, 
  30.  
  31.    ``I tower you,'' i.e., 2^2^2...^2, n times. 
  32.  
  33. In fact he could have said: ``I Ackerman you,'' which really means 
  34. ``I diagonalize you''.
  35.  
  36. So in some sense, the game can be viewed as happening on the recursive
  37. hierarchy with a move taking you from one limit to another.  For
  38. example, after B says ``I diagonalize you'', A responds with ``I
  39. diagonalize you'', which means ``I diagonalize your diagonalization''.
  40. E.g., you diagonalize the using the Ackerman function, by
  41. diagonalizing the sequence
  42.  
  43. B_1(n, k) = Ackerman(Ackerman...(Ackerman(n)))   (k Ackerman's)
  44.  
  45. B_2(n, k) = B_2(n, B_1(n, k-1))
  46.  
  47. i.e., the function you end up with is essentially
  48.  
  49.   C(n) = B_n(n, n) 
  50.  
  51. up to some fussing about whether n -> n-1 or not.
  52.  
  53. Such moves seem to be optimal, in some sense.
  54.  
  55. -ilan
  56.  
  57.  
  58.  
  59.