home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10193 < prev    next >
Encoding:
Internet Message Format  |  1992-08-12  |  4.4 KB
  1. Path: sparky!uunet!comp.vuw.ac.nz!waikato.ac.nz!canterbury.ac.nz!math!wft
  2. Newsgroups: sci.math
  3. Subject: re: Puzzles
  4. Message-ID: <1992Aug13.130820.313@csc.canterbury.ac.nz>
  5. From: wft@math.canterbury.ac.nz (Bill Taylor)
  6. Date: 13 Aug 92 13:08:16 +1200
  7. Distribution: world
  8. Organization: Department of Mathematics, University of Canterbury
  9. Nntp-Posting-Host: math.canterbury.ac.nz
  10. Lines: 83
  11.  
  12. Firstly, thanks to John Baez for his excellent and intriguing post (as always).
  13.  
  14. I personally thought it was fascinating to see how EVERY FINITE STRING of
  15. digits can appear at the beginning of a number of the form 2^n. I fully
  16. approve of John Baez's polite but dismissive rebuttal of the suggestion
  17. that it was *merely* a trivial consequence of a density-of-reals result,
  18. (though this observation was also interesting).
  19.  
  20. Puzzle # 1, "SMOOTH SHARP CORNERS?", was a lot of fun, and I have already
  21. posted my solution to that.
  22.  
  23. Puzzle # 2, "THE COMPLEXITY BARRIER", was fascinating too, and interesting to
  24. see in this form. [ I dimly recall seeing this result before, but can't think
  25. how the proof goes now. I haven't checked my references before posting; of
  26. course I should've, but why be different from 90% of all posters  :-) ]
  27.  
  28. Anyway, I thought I'd send in a few idle musings on this subject, though
  29. they'll mainly come under the heading of SILLY REMARKS. Still, they might amuse.
  30. ---
  31.  
  32. John presents the Almost-Paradox
  33.  
  34. [A-P] (1) it is provable that "for almost all n, P(n)".
  35.       (2) for any particular N, it is not provable that "P(N)".
  36.  
  37. In this case, P(n) is the statement that n cannot be produced by a program
  38. of length <= E.  E is unspecified, but a value can be calculated (in principle).
  39.  
  40. Now my first reaction to this meta-theorem is that it's clearly not true
  41. unless the "any particular N" in (2) is a bit more closely specified.
  42. For instance, it follows from (1) that we can define a unique number M, by
  43. M = smallest positive integer requiring a program of length > E.
  44.  
  45. Now this (unambiguously defined) M  satisfies P, (by definition).
  46. Shades of "the smallest uninteresting number" !
  47. However most people would rightly consider this to be a bit of a cheat.
  48. So it looks like the N in (2) should be restricted by e.g. the requirement that
  49. it be presented in numeral form.  Of course to actually *make* this presentation
  50. is going to require a huge amount of paper (or whatever), so the meta-theorem
  51. is already starting to look a little less startling; unless.....
  52.  
  53. [Question 1] ....can any less restrictive condition than "N in numeral form"
  54. ~~~~~~~~~~~  be used in (2), that will preserve the truth of [A-P] ?
  55.  
  56. This relates to the whole grisly matter of when is an integer "properly
  57. specified", which continues to bedevil metamathematics (for instance, the
  58. number F which = 9 if FLT is false, and 8 if true). Though many people would
  59. probably say F is not "really" defined properly (yet), at least we know it
  60. a lot more accurately than the "better"-defined M above !
  61.  
  62. Anyway, I would also like to see an answer to
  63.  
  64. [Question 2] What is a good value for E ?
  65. ~~~~~~~~~~~ (I don't recall seeing an answer posted; I can't even guess at it.)
  66.  
  67. [Question 3] Are there any "more natural" properties P, to which [A-P] applies ?
  68. ~~~~~~~~~~~  i.e. more traditionally mathematical than the logico-computing
  69.                   property P given above.
  70.  
  71.  
  72. As a final bit of nonsensical musing on [A-P] as given; I got into the
  73. following grand wild goose chase.                     I was trying to
  74. imagine finding a number G, such that we could be reasonably sure (short of
  75. a proof), that *all* numbers greater than G would need programs of length > E.
  76.  
  77. Clearly it would have to be at least as large as 10^n, where n also had
  78. this property (or nearly had it). This means in turn it would have to be
  79. larger than 10^10^...^10, with 10^n exponentiations. This in turn would
  80. mean that it would have to be........ (getting well into Ackerman's function)
  81.  
  82. Indeed, there's no end to the quest, seemingly, short of irreparable brain
  83. damage. It would be nice to see a reasonable answer to Question 2, though.
  84. It presumably would have some bearing on this wild goose chase.
  85.  
  86. ----
  87. Thanks again John, for a fun post.
  88.  
  89. ---------------------------------------------------------------------
  90.       Bill Taylor              wft@math.canterbury.ac.nz
  91. ---------------------------------------------------------------------
  92. Well, I believe in solipsism, but that's just one man's opinion.
  93. ---------------------------------------------------------------------
  94.  
  95.