home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / rec / puzzles / 8152 < prev    next >
Encoding:
Internet Message Format  |  1992-12-28  |  2.1 KB
  1. Path: sparky!uunet!digex.com!kfl
  2. From: kfl@access.digex.com (Keith F. Lynch)
  3. Newsgroups: rec.puzzles
  4. Subject: "Vesterman's paradox"
  5. Date: 28 Dec 1992 19:07:12 GMT
  6. Organization: Express Access Public Access UNIX, Greenbelt, Maryland USA
  7. Lines: 35
  8. Distribution: world
  9. Message-ID: <1hnj90INN4f5@mirror.digex.com>
  10. References: <92351.132601RVESTERM@vma.cc.nd.edu> <1gp8ttINNik@gap.caltech.edu> <92352.045047RVESTERM@vma.cc.nd.edu>
  11. NNTP-Posting-Host: access.digex.com
  12.  
  13. Bob Vesterman, <RVESTERM@vma.cc.nd.edu> claims that it's a paradox that:
  14.  
  15. 1) "The smallest positive integer too small to be specified in 150 ASCII
  16.    characters" doesn't exist, since if it did, it has just been specified
  17.    in fewer than 150 characters.
  18.  
  19. 2) There are a finite number of ASCII character strings with length 150
  20.    or less.
  21.  
  22. 3) There are an infinite number of positive integers.
  23.  
  24. The resolution lies in the fact that there's no unique mapping of
  25. character strings onto integers.  "The smallest..." only makes sense
  26. in terms of some mapping.  One mapping would be to use nothing but the
  27. digits 0 through 9, in the usual way.  In that case, 10^151 is the
  28. smallest positive integer which cannot be specified in 150 characters.
  29. If we use base 256 notation, using the full eight-bit ASCII set, then
  30. 256^150 is the answer.  These two mappings have the virtue of being able
  31. to represent any positive integer less than this limit.
  32.  
  33. What if our mapping includes the digits 0 through 9 and the symbols
  34. + - * / ^ to be used in the usual way?  Then the highest number that
  35. can be represented is 9^9^9^9^9...9^9^99 (note that the number one less
  36. than this cannot be represented).
  37.  
  38. Since there are no restrictions on possible mappings, there is no highest
  39. integer that can be represented in 150 characters.  Or in 1 character.
  40. I could take hundreds of megabytes describing what number I mean by "N",
  41. and then giving the string "N", representing whatever mind-bogglingly
  42. large number I defined it as.
  43.  
  44. Of course you can devise meta-mappings, i.e. languages for describing
  45. mappings, but that doesn't change the essense of this argument.
  46.  
  47. Keith Lynch, kfl@access.digex.com
  48.