home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10351 < prev    next >
Encoding:
Text File  |  1992-08-17  |  1.4 KB  |  32 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!secapl!Cookie!frank
  3. From: frank@Cookie.secapl.com (Frank Adams)
  4. Subject: Re: Puzzles
  5. Message-ID: <1992Aug17.222412.56760@Cookie.secapl.com>
  6. Date: Mon, 17 Aug 1992 22:24:12 GMT
  7. References: <1992Aug13.130820.313@csc.canterbury.ac.nz>
  8. Organization: Security APL, Inc.
  9. Lines: 21
  10.  
  11. In article <1992Aug13.130820.313@csc.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes:
  12. >John presents the Almost-Paradox
  13. >
  14. >[A-P] (1) it is provable that "for almost all n, P(n)".
  15. >      (2) for any particular N, it is not provable that "P(N)".
  16. >
  17. >In this case, P(n) is the statement that n cannot be produced by a program
  18. >of length <= E.  E is unspecified, but a value can be calculated (in principle).
  19. >
  20. >As a final bit of nonsensical musing on [A-P] as given; I got into the
  21. >following grand wild goose chase.                     I was trying to
  22. >imagine finding a number G, such that we could be reasonably sure (short of
  23. >a proof), that *all* numbers greater than G would need programs of length > E.
  24. >
  25. >Clearly it would have to be at least ...
  26. >
  27. If the formal system involved is at all powerful, it would have to be bigger
  28. than anything you can come up with.  We're talking about the busy beaver
  29. problem here, into the range where even the size of the program is (by
  30. conventional standards) rather large.  You can be sure that the smallest
  31. such G is absolutely, unimaginably, large.
  32.