home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / theory / 2715 < prev    next >
Encoding:
Text File  |  1992-12-16  |  2.2 KB  |  47 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!elroy.jpl.nasa.gov!swrinde!ringer!djimenez
  3. From: djimenez@ringer.cs.utsa.edu (Daniel Jimenez)
  4. Subject: Re: Real Numbers vs. Rational Numbers?
  5. Message-ID: <1992Dec16.222628.27208@ringer.cs.utsa.edu>
  6. Organization: University of Texas at San Antonio
  7. References: <1992Dec16.095412.19570@tom.rz.uni-passau.de>
  8. Date: Wed, 16 Dec 1992 22:26:28 GMT
  9. Lines: 36
  10.  
  11.  
  12. In article <1992Dec16.095412.19570@tom.rz.uni-passau.de> boerncke@kirk.fmi.uni-passau.de (Frank-Roland Boernke) writes:
  13. >In lectures we talked about the RAM, a formal machine-model that is proved
  14. >to be as powerful as turing-machines(TM) and vice versa, according to the
  15. >Church-Turing-Thesis. This seems to be ok until you say, that the RAM allows
  16. >only natural numbers in its registers (or rational-numbers, since they are 
  17. >countable). Our professor told us, that RAMs are allowed to store REAL numbers
  18. >too AND they are  still as powerful as an ordinary turing machine. I claimed, this
  19. >can`t be true, since there isn`t any possibility to work with irrational 
  20. >numbers in TMs. 
  21. >
  22. >Of course, e.g. you can compute Pi up to as many digits as you want, but in every
  23. >step  of computation you only have an approximation - a rational number.
  24. >
  25. >Therefore, a machine-model, that allows real numbers, must be more powerful
  26. >than another one that does not. My professor said, that isn`t a problem but
  27. >I don`t agree. Who is right?
  28. >
  29. >If I am wrong, please let me know where the fault is.
  30.  
  31. How about this: 
  32. Maybe the model could conceivably represent the reals, but how would any
  33. irrational number get into the machine in the first place?  There are 
  34. uncountably many irrationals, so a table look-up won't do.  You could
  35. try to calculate them, but how do you calculate, say, pi, with only 
  36. Turing-machine-like operations?
  37.  
  38. So, at first glance, it looks like this machine is equivalent to the RAM
  39. model with rationals plus a finite number of irrationals you could have in
  40. a table.  This is equivalent to a Turing machine.
  41.  
  42. Anybody buy that?
  43. -- 
  44. Daniel Jimenez                     djimenez@ringer.cs.utsa.edu
  45. "I've so much music in my head" -- Maurice Ravel, shortly before his death.
  46. "                             " -- John Cage
  47.