Article View: comp.theory
Article #1736Re: Real Numbers vs. Rational Numbers?
From: Eddie Grove
Date: Thu, 17 Dec 1992 18:59
Date: Thu, 17 Dec 1992 18:59
24 lines
1563 bytes
1563 bytes
In article <1992Dec16.095412.19570@tom.rz.uni-passau.de> boerncke@kirk.fmi.uni-passau.de (Frank-Roland Boernke) writes:
>countable). Our professor told us, that RAMs are allowed to store REAL numbers
>too AND they are still as powerful as an ordinary turing machine. I claimed, this
>can`t be true, since there isn`t any possibility to work with irrational
>numbers in TMs.
The assumption of a RAM that uses real numbers is that you can store a real
number in one memory location.
It all comes down to whether you allow constants.
If you do allow constants, consider the real number U whose i^th bit is
true if (in some standard encoding) the i^th turing machine halts when
given i as input.
Given U, and the ability to do standard arithmetic operations on intermediate
results (mult by 2, compare to integer, subtract integer from) you can
decide the language {i : machine i does not halt on i}, which is beyond
the range of an ordinary TM.
If you do not allow real constants, you can simulate the "REAL" RAM by an
ordinary TM.
Eddie Grove
Technical Details
Message-ID:
<1gqimoINNeos@agate.berkeley.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!zaphod.mps.ohio-state.edu!caen!spool.mu.edu!agate!triangle.Berkeley.EDU!groveReferences:
<1992Dec16.095412.19570@tom.rz.uni-passau.de>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!zaphod.mps.ohio-state.edu!caen!spool.mu.edu!agate!triangle.Berkeley.EDU!grove From: grove@triangle.Berkeley.EDU (Eddie Grove) Newsgroups: comp.theory Subject: Re: Real Numbers vs. Rational Numbers? Date: 17 Dec 1992 18:59:36 GMT Organization: University of California, Berkeley Lines: 24 Distribution: inet Message-ID: <1gqimoINNeos@agate.berkeley.edu> References: <1992Dec16.095412.19570@tom.rz.uni-passau.de> NNTP-Posting-Host: triangle.berkeley.edu