Timeline for Represent a real number without loss of precision
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 11, 2017 at 14:41 | comment | added | Andrej Bauer | Consider Chaitin's constant $\Omega$, a real number which is not computable. Please describe a program with access to the random number generator that represents $\Omega$. Note: you do not get to redefine "program $p$ represents real number $x$", that is a fixed notion. It means: on input $k$ program $p$ outputs a rational number $s$ such that $|x - s| < 2^{-k}$. I do not see how a random number generator helps you get $\Omega$. I will even buy a program which represents $\Omega$ with some positive probability, to make your task seemingly easier. | |
| Aug 11, 2017 at 13:24 | comment | added | wlad | I want to add: The set of real numbers that are representable as source code does not necessarily equal the computable numbers, even under the Church-Turing thesis. If the code is allowed access to a true random number generator, then all the real numbers are representable. I find this to be an easy philosophical justification for why the set of all real numbers is preferable to the set of computable numbers, even in computer science. | |
| Nov 28, 2015 at 17:19 | comment | added | Andrej Bauer | These remarks about countability are irrelevant because the computable reals are not computably countable. | |
| Nov 28, 2015 at 17:18 | comment | added | ARi | Hence what you term as working with reals I'd no different from working with the set of natural numbers,ie is only a countable subset of reals. | |
| Nov 28, 2015 at 17:11 | comment | added | ARi | @AndrejBauer The point is that the set of computable reals(based on any model of computation) has one to one corres pondance with set of finite strings.No matter what you do a Turing machine can only exhaustively represent a countable set. | |
| Jul 14, 2014 at 8:23 | comment | added | Andrej Bauer | @Thomas: symbolic computation does not represent real numbers, but usually some subfield of the reals, typically the one generated by elementary functions and roots of polynomials. These subfields are not complete (closed under limits of Cauchy sequences) nor computably complete (closed under computable limits of Cauchy sequences). A representation is not a representation of reals unless you can represent all (computable) reals: and symbolic computations fails this condition. | |
| Jul 12, 2014 at 16:10 | comment | added | Gilles 'SO- stop being evil' | @Thomas Remember that the stream of digits is a representation of numbers. Equality of the numbers is not equivalent with equality of the streams. What you need to do is not “process all the information”, but decide based on finite information. If you approximate a stream of digits with an initial sequence of its values, this approximation is not good enough to decide equality. | |
| Jul 12, 2014 at 13:50 | comment | added | Thomas | @AndrejBauer But you must access or process all the information at once in some cases, e.g. this is what symbolic computation does, by capturing the "essence" or nature of a quantity rather than just as any other stream of digits. If you tell a symbolic computation package to verify that $\sqrt{2}^2 = 2$, it would instantly output true. If you used the method you seem to describe, by taking the first $k$ digits of the square root of $2$, for any $k$ you will conclude that $\sqrt{2}^2 \ne 2$ as your result will (for any finite $k$) equal $1.99...$, wrong answer. Computations are finite. | |
| Jul 12, 2014 at 11:25 | comment | added | Andrej Bauer | The point is that we are not representing with finite strings. We are representing with infinite strings, but we only ever need a finite portion of such an infinite string at each stage of computation. Or to put it another way: there is no loss of precisions, as the data structure holds the entire information, but of course you cannot access or process all of the information at once: the data structure gives you as much precision as you ask for. The bottleneck is not on the side of the data structure, but rather on the side of the "consumer" who want to get the information out of it. | |
| Jul 12, 2014 at 9:17 | comment | added | David Richerby | +1 but I would object that you can't represent an infinite string by a finite approximation without losing precision, as required by the question. Sure, you can get as much precision as you want -- as you could by approximating by a rational -- but that's not quite what the question's asking for. Arguably, that's a problem with the question, rather than the answer. | |
| Jul 12, 2014 at 8:58 | history | edited | Andrej Bauer | CC BY-SA 3.0 |
added 127 characters in body
|
| Jul 12, 2014 at 8:52 | history | edited | Andrej Bauer | CC BY-SA 3.0 |
added 127 characters in body
|
| Jul 12, 2014 at 8:46 | history | answered | Andrej Bauer | CC BY-SA 3.0 |