<p>The first theorem of the form you are asking about was proved by Y. Moschovakis in <a href="http://www.numdam.org/item/CM_1965-1966__17__40_0/" rel="nofollow noreferrer"><em>Notation systems and recursive ordered fields</em></a>, Compositio Mathematica 17:40–71 (1965). Then in the context of Type Two Effectivity a similar theorem was proved by P. Hertling, see <a href="https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.19990450202" rel="nofollow noreferrer"><em>A real number structure that is effectively categorical</em></a>, Mathematical Logic Quarterly, 45(2):147–182 (1999). A generalization of these results (and several others) was proved by A. Bauer and J. Blanck in <a href="https://www.jucs.org/jucs_16_18/canonical_effective_subalgebras_of/" rel="nofollow noreferrer"><em>Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions</em></a>, Journal of Universal Computer Science, vol 16:2496–2522 (2010).</p>
<p>The paper I wrote with Jens is very general and maybe less accessible. Another good source to read about this is Peter Hertling's <a href="https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/057hertling.pdf" rel="nofollow noreferrer">The Real Number Structure is Effectively Categorical</a>.</p>
<p>I have nothing intelligent to say about computational complexity.</p>

CC BY-SA 3.0
2014-12-12T01:48:42.237Z
I guess that the computational complexity would be $P− time$, without much reason, and the minimal length of the program is very short.
XL _At_Here_There
CC BY-SA 3.0
2014-12-12T10:45:24.330Z
I am not sure. You could have a silly representation of reals. Pick an arbitrary computable subset $S \subseteq \mathbb{Q}$ of rationals. I could define that a real $x$ is encoded by a sequence $(q_n, b_n)_n$ where $(q_n)_n$ is a sequence of rationals which converge fast to $x$, and $b_n \in \{0,1\}$ is 1 iff $q_n \in S$. Now to convert from the usual representation of reals to this one, you need to calculate whether $q_n \in S$, and the complexity of that can be arbitrarily high. So I very much doubt you get just polytime.
Andrej Bauer
CC BY-SA 4.0
2014-12-11T22:59:53.583Z
2022-04-23T11:29:37.647Z
2022-04-23T11:29:37.647Z
Andrej Bauer
<p>To turn my comment into an answer...</p>

<p>Andrej Bauer in this <a href="https://cstheory.stackexchange.com/questions/16512/is-it-possible-to-test-if-a-computable-number-is-rational-or-integer/16547#16547">post</a> makes the parenthetical claim </p>

<blockquote>
  <p>An important theorem states that any two representations of reals which are acceptable are actually computably isomorphic.</p>
</blockquote>

<p>He never explicitly defines acceptable or cites the theorem. I assume the OPs question is the following.</p>

<p><strong>What theorem is Andrej Bauer referring to?</strong></p>

<p>Here is a guess.  It seems that earlier in the post, Andrej is implicitly suggesting that an acceptable representation of the reals is one in which the following properties hold:</p>

<ol>
<li>One can effectively approximate a real by a rational to within a given precision.</li>
<li>Addition, multiplication, and inverse are computable.</li>
<li>The less-then relation, $&lt;$, is semi-decidable.</li>
<li>There is a computable function which takes in a rapid sequence of reals (that is a sequence $(x_n)$ of reals such that $|x_n - x_m| \leq 2^{\min{n,m}}$ and outputs the limit.</li>
</ol>

<p>Actually (1) and (4) are enough to prove (2) and (3), since to preform those operations: one only needs to approximate the real by a rational, do the operation, and convert back to a real.  (Basic module of continuity will tell you how close the approximated answer is.  Also, one needs to be able to convert from a rational to the corresponding real.  This can be done by using (1) to find reals that are close enough to the rational, and then using (4) to take the limit of these approximations.)</p>

<p>Now, for any two representations satisfying (1) and (4) they are computably isomorphic.  From (1), one can go from the first representation to the rapid Cauchy representation.  (That is, represent a real as a rapid Cauchy sequence of rationals.)  From (4), one can go the other way, taking a rapid Cauchy sequence of rationals and computing the real it converges to (using the second representation).</p>

<p>As for the question about complexity, I think it can't be anything better than just computable, but I realize I don't know for sure, mostly, because I don't know how to formulate the question formally.</p>

CC BY-SA 3.0
2014-12-12T01:14:45.300Z
"Which representations are appropriate for doing real number computations? We show that with respect to computable equivalence there is one and only one equivalence class of representations of the real numbers which make the basic operations computable."cited from : onlinelibrary.wiley.com/doi/10.1002/malq.19990450202/abstract, this possibly is the definition of "acceptable"
XL _At_Here_There
CC BY-SA 3.0
2014-12-11T15:08:27.950Z
2014-12-11T15:08:27.950Z
2017-04-13T12:32:28.167Z
Jason Rute
<p>"any two representations of reals which are acceptable are actually computably isomorphic",please see <a href="https://cstheory.stackexchange.com/questions/16512/is-it-possible-to-test-if-a-computable-number-is-rational-or-integer/16547#16547">here</a> for reference</p>

<p>where may proof of  this theorem   be found, and what is the the computational complexity of the computably isomorphic maps?</p>

CC BY-SA 3.0
2014-12-11T03:11:21.323Z
Define "acceptable".
Tyson Williams
CC BY-SA 3.0
2014-12-11T03:13:50.243Z
@TysonWilliams, see http://cstheory.stackexchange.com/questions/16512/is-it-possible-to-test-if-a-computable-number-is-rational-or-integer/16547#16547
XL _At_Here_There
CC BY-SA 3.0
2014-12-11T03:14:34.353Z
Please make your question self contained.
Tyson Williams
CC BY-SA 3.0
2014-12-11T14:26:40.040Z
In the referenced post, Andrej Bauer makes the parenthetical claim "(An important theorem states that any two representations of reals which are acceptable are actually computably isomorphic.)"  He never explicitly defines acceptable or cites the theorem. I assume the OPs question is really, What theorem is Andrej Bauer referring to?  (An answer to this question would also answer @TysonWilliams question about what does "acceptable" mean.)
Jason Rute
CC BY-SA 3.0
2014-12-12T01:06:54.127Z
@TysonWilliams,"Which representations are appro-
priate for doing real number computations? We show that with respect to computable
equivalence there is one and only one equivalence class of representations of the real
numbers which make the basic operations computable."cited from : http://onlinelibrary.wiley.com/doi/10.1002/malq.19990450202/abstract, this possibly is the definition of "acceptable"
XL _At_Here_There
<cc.complexity-theory><reference-request><computability><computable-analysis>
Where can I find the proof of the theorem and what is the computational complexity of the computably isomorphic map?
XL _At_Here_There
# Where can I find the proof of the theorem and what is the computational complexity of the computably isomorphic map?

(Asked by: username_0 on 2014-12-11)

"any two representations of reals which are acceptable are actually computably isomorphic",please see [here](https://cstheory.stackexchange.com/questions/16512/is-it-possible-to-test-if-a-computable-number-is-rational-or-integer/16547#16547) for reference

where may proof of this theorem be found, and what is the the computational complexity of the computably isomorphic maps?

**Tags:** cc.complexity-theory, reference-request, computability, computable-analysis
> **Comments:**
> **username_1**: Define "acceptable".  
> **username_0**: @TysonWilliams, see http://cstheory.stackexchange.com/questions/16512/is-it-possible-to-test-if-a-computable-number-is-rational-or-integer/16547#16547  
> **username_1**: Please make your question self contained.  
> **username_2**: In the referenced post, Andrej Bauer makes the parenthetical claim "(An important theorem states that any two representations of reals which are acceptable are actually computably isomorphic.)"  He never explicitly defines acceptable or cites the theorem. I assume the OPs question is really, What theorem is Andrej Bauer referring to?  (An answer to this question would also answer @TysonWilliams question about what does "acceptable" mean.)  
> **username_0**: @TysonWilliams,"Which representations are appro- priate for doing real number computations? We show that with respect to computable equivalence there is one and only one equivalence class of representations of the real numbers which make the basic operations computable."cited from : http://onlinelibrary.wiley.com/doi/10.1002/malq.19990450202/abstract, this possibly is the definition of "acceptable"  

---

## 2 answers

### Answer by username_3 on 2014-12-11. Score: 3 | Accepted answer

The first theorem of the form you are asking about was proved by Y. Moschovakis in [*Notation systems and recursive ordered fields*](http://www.numdam.org/item/CM_1965-1966__17__40_0/), Compositio Mathematica 17:40–71 (1965). Then in the context of Type Two Effectivity a similar theorem was proved by P. Hertling, see [*A real number structure that is effectively categorical*](https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.19990450202), Mathematical Logic Quarterly, 45(2):147–182 (1999). A generalization of these results (and several others) was proved by A. Bauer and J. Blanck in [*Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions*](https://www.jucs.org/jucs_16_18/canonical_effective_subalgebras_of/), Journal of Universal Computer Science, vol 16:2496–2522 (2010).

The paper I wrote with Jens is very general and maybe less accessible. Another good source to read about this is Peter Hertling's [The Real Number Structure is Effectively Categorical](https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/057hertling.pdf).

I have nothing intelligent to say about computational complexity.

> **Comments:**
> **username_0**: I guess that the computational complexity would be $P− time$, without much reason, and the minimal length of the program is very short.  
> **username_3**: I am not sure. You could have a silly representation of reals. Pick an arbitrary computable subset $S \subseteq \mathbb{Q}$ of rationals. I could define that a real $x$ is encoded by a sequence $(q_n, b_n)_n$ where $(q_n)_n$ is a sequence of rationals which converge fast to $x$, and $b_n \in \{0,1\}$ is 1 iff $q_n \in S$. Now to convert from the usual representation of reals to this one, you need to calculate whether $q_n \in S$, and the complexity of that can be arbitrarily high. So I very much doubt you get just polytime.  

---

### Answer by username_2 on 2014-12-11. Score: 3

To turn my comment into an answer...

Andrej Bauer in this [post](https://cstheory.stackexchange.com/questions/16512/is-it-possible-to-test-if-a-computable-number-is-rational-or-integer/16547#16547) makes the parenthetical claim

> An important theorem states that any two representations of reals which are acceptable are actually computably isomorphic.

He never explicitly defines acceptable or cites the theorem. I assume the OPs question is the following.

**What theorem is Andrej Bauer referring to?**

Here is a guess. It seems that earlier in the post, Andrej is implicitly suggesting that an acceptable representation of the reals is one in which the following properties hold:

1. One can effectively approximate a real by a rational to within a given precision.
2. Addition, multiplication, and inverse are computable.
3. The less-then relation, $<$, is semi-decidable.
4. There is a computable function which takes in a rapid sequence of reals (that is a sequence $(x\_n)$ of reals such that $|x\_n - x\_m| \leq 2^{\min{n,m}}$ and outputs the limit.

Actually (1) and (4) are enough to prove (2) and (3), since to preform those operations: one only needs to approximate the real by a rational, do the operation, and convert back to a real. (Basic module of continuity will tell you how close the approximated answer is. Also, one needs to be able to convert from a rational to the corresponding real. This can be done by using (1) to find reals that are close enough to the rational, and then using (4) to take the limit of these approximations.)

Now, for any two representations satisfying (1) and (4) they are computably isomorphic. From (1), one can go from the first representation to the rapid Cauchy representation. (That is, represent a real as a rapid Cauchy sequence of rationals.) From (4), one can go the other way, taking a rapid Cauchy sequence of rationals and computing the real it converges to (using the second representation).

As for the question about complexity, I think it can't be anything better than just computable, but I realize I don't know for sure, mostly, because I don't know how to formulate the question formally.

> **Comments:**
> **username_0**: "Which representations are appropriate for doing real number computations? We show that with respect to computable equivalence there is one and only one equivalence class of representations of the real numbers which make the basic operations computable."cited from : onlinelibrary.wiley.com/doi/10.1002/malq.19990450202/abstract, this possibly is the definition of "acceptable"  

---

