home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11326 < prev    next >
Encoding:
Text File  |  1992-09-12  |  2.1 KB  |  58 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!jvnc.net!yale.edu!cs.yale.edu!!rabin
  3. From: rabin@CS.Yale.Edu (Dan Rabin)
  4. Subject: Re: computable reals
  5. In-Reply-To: lucas@WATSON.IBM.COM's message of 12 Sep 92 04: 24:12 GMT
  6. Message-ID: <RABIN.92Sep12155227@epic.CS.Yale.Edu>
  7. Sender: news@cs.yale.edu (Usenet News)
  8. Nntp-Posting-Host: epic.systemsz.cs.yale.edu
  9. Reply-To: rabin-dan@cs.yale.edu
  10. Organization: Computer Science, Yale University, New Haven, CT 06520-2158
  11. References: <9209120452.AA03328@ucbvax.Berkeley.EDU>
  12. Date: Sat, 12 Sep 1992 15:52:27 GMT
  13. Lines: 43
  14.  
  15. Bruce Lucas asks about the set of computable reals.  
  16.  
  17. Unfortunately, if you're hoping to use them in programs, numeric
  18. comparisons are undecidable: Asking whether any arbitrary computable
  19. real is zero is exactly the same as asking whether its defining
  20. digit-producing program ever cranks out a non-zero digit.  That's not
  21. decidable.  Oops.
  22.  
  23. Of course, this is not a deficiency with respect to the entire set of
  24. real numbers, which has this problem plus the problem that some
  25. (almost all, actually ;-))of its
  26. elements aren't finitely representable in the first place.  It's only
  27. a deficiency if you thought that moving from floating point to
  28. computable-reals in a computer program would be a smooth transition.
  29.  
  30. There is a literature on this subject within computer science.  
  31. Here are a couple of initial pointers:
  32.  
  33. @incollection{boehm-cartwright:exact-reals,
  34.   author =     {Hans Boehm and Robert Cartwright},
  35.   title =     {Exact Real Arithmetic: Formulating Real Numbers as
  36.                 Functions},
  37.   editor =    {David A. Turner},
  38.   chapter =     {3},
  39.   booktitle =     {Research Topics in Functional Programming},
  40.   year =     {1990},
  41.   series =     {The UT Year of Programming Series},
  42.   publisher =     {Addison-Wesley Publishing Company, Inc.},
  43. }
  44.  
  45. @InProceedings{vuillemin:exact-real,
  46.   author =     "Jean Vuillemin",
  47.   title =     "Exact Real Computer Arithmetic with Continued
  48.          Fractions",
  49.   pages =     {14--27},
  50.   booktitle =     "Proceedings of the 1988 {ACM} Conference on {L}isp
  51.          and Functional Programming",
  52.   year =     "1988",
  53.   month =     "July",
  54. }
  55.  
  56.   -- Dan Rabin
  57.      rabin-dan@cs.yale.edu
  58.