home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / theory / 2725 < prev    next >
Encoding:
Internet Message Format  |  1992-12-17  |  1.5 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!caen!spool.mu.edu!agate!triangle.Berkeley.EDU!grove
  2. From: grove@triangle.Berkeley.EDU (Eddie Grove)
  3. Newsgroups: comp.theory
  4. Subject: Re: Real Numbers vs. Rational Numbers?
  5. Date: 17 Dec 1992 18:59:36 GMT
  6. Organization: University of California, Berkeley
  7. Lines: 24
  8. Distribution: inet
  9. Message-ID: <1gqimoINNeos@agate.berkeley.edu>
  10. References: <1992Dec16.095412.19570@tom.rz.uni-passau.de>
  11. NNTP-Posting-Host: triangle.berkeley.edu
  12.  
  13. In article <1992Dec16.095412.19570@tom.rz.uni-passau.de> boerncke@kirk.fmi.uni-passau.de (Frank-Roland Boernke) writes:
  14. >countable). Our professor told us, that RAMs are allowed to store REAL numbers
  15. >too AND they are  still as powerful as an ordinary turing machine. I claimed, this
  16. >can`t be true, since there isn`t any possibility to work with irrational 
  17. >numbers in TMs. 
  18.  
  19. The assumption of a RAM that uses real numbers is that you can store a real 
  20. number in one memory location.
  21.  
  22. It all comes down to whether you allow constants.  
  23.  
  24. If you do allow constants, consider the real number U whose i^th bit is
  25. true if (in some standard encoding) the i^th turing machine halts when
  26. given i as input.
  27.  
  28. Given U, and the ability to do standard arithmetic operations on intermediate
  29. results (mult by 2, compare to integer, subtract integer from) you can 
  30. decide the language {i : machine i does not halt on i}, which is beyond 
  31. the range of an ordinary TM.
  32.  
  33. If you do not allow real constants, you can simulate the "REAL" RAM by an
  34. ordinary TM.
  35.  
  36. Eddie Grove
  37.