<p>I am not exactly sure what the question is here, but I can try to say a bit to clean up possible misunderstandings.</p>

<p>First of all, if we are talking about complexity of a map $f : \mathbb{R} \to \mathbb{R}$, it makes <em>no sense</em> to ask "What is a good representation for $\sqrt{2}$?" Instead, you have to ask "What is a good representation for <em>all</em> inputs of $f$?". Compare the situation with an easier one in discrete math: when you discuss an algorithm which takes a graph as an input, you do not ask "Should we represent the Petersen graph as as an adjancency list or as a binary matrix?" but instead you automatically think of a <em>uniform</em> representation which will work for all graphs.</p>

<p>Another word of warning. By changing the representation of the input data we can <em>always</em> make any problem (including a non-computable one) trivially computable: in order to make $f : A \to B$ computable, represent the elements of $A$ as pairs $(a, f(a))$. Then you can "compute" $f$ by the second projection. This shows that we need clear criteria of what it means to represent data.</p>

<p>I have written on several occasions about what it takes to represent the elements of $\mathbb{R}$. The answer depends on what <em>structure</em> of $\mathbb{R}$ you are trying to capture. If you are trying to capture no structure, then you can represent all reals with the empty list, for example. A reasonable list of conditions for a representation of $\mathbb{R}$ is that it needs to be such that:</p>

<ol>
<li>The arithmetical operations $+$, $\times$, $-$, $/$ are computable, as well as the absolute value $|{-}|$.</li>
<li>There is a program which takes (the representation of) a real $x$ and $k \in \mathbb{N}$ and outputs integers $p, q$ such that $|x - p/q| \leq 2^{-k}$, i.e., it is possible to compute arbitrarily good rational approximations.</li>
<li>There is a program which takes (representations of) reals $x$ and $y$ and terminates if, and only if, $x &lt; y$, i.e, the strict order is semidecidable.</li>
<li>Given a sequence (of representations of) $(x_n)_n$ such that $|x_{n+1} - x_n| \leq 2^{-n}$ a representation for the limit $\lim_n x_n$ can be computed.</li>
</ol>

<p>There are old theorems (see introduction to <a href="http://www.jucs.org/jucs_16_18/canonical_effective_subalgebras_of" rel="nofollow">this paper</a> for references) which explain why these conditions are the correct one. These theorems also show that any two such representations of reals are computably isomorphic, that is, we can translate between them with programs. This sets up some criteria for correctness that throw out faulty ideas.</p>

<p>For example, I hear people say things like "rational numbers can be represented by finite information, so let's use that for rational numbers, and the irrational numbers will have to be represented by infinite information". This sort of thing does not work because it breaks the fourth condition above (consider a limit of irrational numbers -- how will you tell that it is converging to a rational?).</p>

<p>Another example which the above conditions eliminate is the Blum-Shub-Smale model because in it you cannot compute limits of sequences. It is better to say that the BSS model works on a discrete ordered subfield of reals (generated by whatever parameters are present), not on the reals themselves.</p>

<p>Among the correct representations of reals some are more efficient than others, although this is a somewhat difficult topic to discuss because real numbers are infinite objects. Matthias Schröder <a href="http://homepages.inf.ed.ac.uk/als/Research/Others/schroeder-mlq04.pdf" rel="nofollow">pointed out</a> that for a reasonable theory of complexity one has to pay attention to the topological properties of the representation.</p>

<p>Finally, <em>how</em> should we measure the complexity of a map $f : \mathbb{R} \to \mathbb{R}$, assuming we have a good representation of $\mathbb{R}$? Because $x \in \mathbb{R}$ is represented by a function, or an infinite stream of information, or some such, we should be using one of the <a href="http://www.cis.syr.edu/~royer/bib2.html" rel="nofollow">higher-type notions of complexity</a>. Which one probably depends on the representation you are using.</p>

<p>The BSS model  is a also a reasonable circuit complexity model in which we count arithmetical operations. It's just good to keep in mind that this model is not about real numbers, but about something else.</p>

CC BY-SA 3.0
2014-11-21T00:47:51.837Z
Thank you very much for your answer, and so many references. I feel uncomfortable about some notions of computational complexity, let me read the reference and think about for a time, and give an example, if I can find suitable one to explain why I am so uncomfortable( this sounds funny, But my experience tell me if I feel uncomfortable, there must be something singular)
XL _At_Here_There
CC BY-SA 3.0
2014-11-21T14:19:05.773Z
In my experience, feeling uncomfortable about new knowledge is a good sign, and usually it is a prerequisite for enlightenment.
András Salamon
CC BY-SA 3.0
2014-11-20T16:34:48.643Z
2014-11-26T07:35:34.500Z
2014-11-26T07:35:34.500Z
Andrej Bauer
<p>Another model possibly to explore, is that of the Feasible RAM model. This is a modified real RAM model for Real computation, Feasible RAM, or a modified RAM model which uses both the discrete, and real valued arithmetic operations. This model allows for real, and discrete operations, and the Turing model, is interchangeable with it. The Feasible RAM model has precision defined with uncertainty, which means that $&lt;_{k}$ allows comparisons of real numbers only up to a variable uncertainty 1/(k+1). This allows for approximative computations. Also, as Vasco Brattkaa and Peter Hertlingb state in <a href="http://www.sciencedirect.com/science/article/pii/S0885064X98904885" rel="nofollow">Feasible Real Random Access Machines</a> - the models of Turing, and that of Feasible Real RAMs, are related. All functions computable on a Turing machine in time $O(t)$ are computable on a RAM in time $O(t)$, and in the obverse case there some overhead for the Turing machine that computes the function(if real RAM computes the function in $O(t)$ the TM computes the function in $O(t^{2}log(t)log(log(t)))$. As pointed out topological considerations are useful, one doesn't know if there is any topological context developed for this model of computation that allows for real computations -which has uncertainty in precision. </p>

CC BY-SA 3.0
2014-11-23T11:09:55.123Z
Could you give some reference for the feasible RAM model?
XL _At_Here_There
CC BY-SA 3.0
2014-11-23T14:05:07.057Z
See above in the area, "... this reference states ..." has a link to the article.
user3483902
CC BY-SA 3.0
2014-11-26T07:41:58.990Z
Thanks for pointing out to the Brattka & Hertling work, I was going to mention it by then I forgot. I would just like to point out that the Feasible RAM model does not include any higher-order functions, in particular it cannot compute the limit of a (rapid) Cauchy sequence, so I would not count it as implementing "the reals" precisely. It can compute one limit "on the top level", so to speak (see the part of the paper where they speak about rational approximations of functions).
Andrej Bauer
CC BY-SA 3.0
2014-11-23T07:46:12.467Z
2014-11-26T08:50:49.640Z
2014-11-26T08:50:49.640Z
user3483902
<p>As we know, definition of computational complexity of algorithm is almost without controversy, but the definition of computational complexity of reals  or the computation models over reals is not in such a case. We know Blum and Smales' model and model in the book Computable Analysis. And seemingly, model in Computable Analysis is consistent with the classic model, but the definition of computational complexity of reals can not transplanted into classic model.</p>

<p>How to judge the definition of computational complexity of reals is natural or suitable?</p>

<p>And how to transplant the definition of computational complexity of reals  into classic model?</p>

CC BY-SA 3.0
2014-11-19T08:02:32.820Z
For your first question, "natural" is a very subjective notion and depending on the person you ask, one or the other definition will be considered as the most natural. As for "suitable", it depends: the BSS model seems suitable for computational geometry or computational algebraic geometry, and the model in Computable Analysis is more suitable for... computable analysis! I do not understand the second question.
Bruno
CC BY-SA 3.0
2014-11-19T08:08:58.633Z
@Bruno, thank you for your comment, I think the model in Computable Analysis, and do not know how to apply the definition of computational complexity to  computation of real number over classic model like Turing Machine, since the computational complexity of real number over model in Computable Analysis depends on the representation of it,namely, the input for computation of it.
XL _At_Here_There
CC BY-SA 3.0
2014-11-19T08:12:27.840Z
@Bruno, that a model is not suitable universally,  implies that it is a special class of model which need to be generalized or expanded. If it can not generalized, it must be unsuitable. In my word, I think natural is equivalent to truth or suitable, maybe what I think about natural is not suitable.
XL _At_Here_There
CC BY-SA 3.0
2014-11-19T14:59:13.937Z
You seem to think there is a complexity notion for real number computation which is independent of the representation of reals. What makes you think so? This is not the case in classical complexity either. It matters whether you have a tape or a RAM machine, it matters whether you represent graphs by adjancency lists or 01-matrices, etc.
Andrej Bauer
CC BY-SA 3.0
2014-11-20T01:56:37.037Z
@AndrejBauer, Thank you for your comment. I don't think there is a complexity notion for real number computation which is independent of the representation of reals. I am puzzled with or wondering why in classical computational complexity, we can have P,NP etc, which is in fact irrelevant to input or the representation, they are only measure of the algorithm, in other word, the computational complexity is measured by hierarchy of functions with n the length of input as parameter. Let me think about it and give an example. Thank you for your helpful comment.
XL _At_Here_There
CC BY-SA 3.0
2014-11-20T12:35:11.193Z
But it's not true that the complexity does not depend on the representation. By switching to a stupid representation you can *always* ruin the complexity of an algorithm. The question to ask is: "What is a *good* representation of the input?" For discrete problems this is much easier to answer than for real numbers, because one has a good feel for what it means to "don't waste bits".
Andrej Bauer
CC BY-SA 3.0
2014-11-20T14:24:14.043Z
@AndrejBauer, Yes, there so many suitable  representations for a computable irrational number of finite length that interact with the computational complexity of it, what is the standard for good represent? And for discrete problem, we just know good by feeling, but clear and rigorious standard. As for computable irrational computable number,like $\sqrt{2}$,  we may have a computable sequence of integers as  coefficients of it's continued fraction, or a representation by program with a Kolmogorov complexity or something related to KC, which one is the best? [to be continued]
XL _At_Here_There
CC BY-SA 3.0
2014-11-20T14:27:26.720Z
And, by representation with KC, we have a universal standard or uniform representation for the input, but program with length of KC is not computable, with a variant of KC, our choice is somehow arbitary, and makes the comparison between reals meaningless or too unstable.
XL _At_Here_There
CC BY-SA 3.0
2014-11-23T15:07:07.007Z
_the BSS model seems suitable for computational geometry_ — See [my answer to a related question](http://cstheory.stackexchange.com/a/2124/111).  The Real RAM model used by computational geometers predates Blum, Shub, and Smale by almost a decade.
Jeffε
CC BY-SA 3.0
2014-11-23T23:19:00.340Z
@JɛﬀE, Thank you for your comment, it'd rather be an answer.
XL _At_Here_There
<cc.complexity-theory><reference-request><computability><computing-over-reals><computable-analysis>
How to judge the definition of computational complexity of reals is natural or suitable?
XL _At_Here_There
# How to judge the definition of computational complexity of reals is natural or suitable?

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

As we know, definition of computational complexity of algorithm is almost without controversy, but the definition of computational complexity of reals or the computation models over reals is not in such a case. We know Blum and Smales' model and model in the book Computable Analysis. And seemingly, model in Computable Analysis is consistent with the classic model, but the definition of computational complexity of reals can not transplanted into classic model.

How to judge the definition of computational complexity of reals is natural or suitable?

And how to transplant the definition of computational complexity of reals into classic model?

**Tags:** cc.complexity-theory, reference-request, computability, computing-over-reals, computable-analysis
> **Comments:**
> **username_1**: For your first question, "natural" is a very subjective notion and depending on the person you ask, one or the other definition will be considered as the most natural. As for "suitable", it depends: the BSS model seems suitable for computational geometry or computational algebraic geometry, and the model in Computable Analysis is more suitable for... computable analysis! I do not understand the second question.  
> **username_0**: @Bruno, thank you for your comment, I think the model in Computable Analysis, and do not know how to apply the definition of computational complexity to  computation of real number over classic model like Turing Machine, since the computational complexity of real number over model in Computable Analysis depends on the representation of it,namely, the input for computation of it.  
> **username_0**: @Bruno, that a model is not suitable universally,  implies that it is a special class of model which need to be generalized or expanded. If it can not generalized, it must be unsuitable. In my word, I think natural is equivalent to truth or suitable, maybe what I think about natural is not suitable.  
> **username_2**: You seem to think there is a complexity notion for real number computation which is independent of the representation of reals. What makes you think so? This is not the case in classical complexity either. It matters whether you have a tape or a RAM machine, it matters whether you represent graphs by adjancency lists or 01-matrices, etc.  
> **username_0**: @AndrejBauer, Thank you for your comment. I don't think there is a complexity notion for real number computation which is independent of the representation of reals. I am puzzled with or wondering why in classical computational complexity, we can have P,NP etc, which is in fact irrelevant to input or the representation, they are only measure of the algorithm, in other word, the computational complexity is measured by hierarchy of functions with n the length of input as parameter. Let me think about it and give an example. Thank you for your helpful comment.  
> **username_2**: But it's not true that the complexity does not depend on the representation. By switching to a stupid representation you can *always* ruin the complexity of an algorithm. The question to ask is: "What is a *good* representation of the input?" For discrete problems this is much easier to answer than for real numbers, because one has a good feel for what it means to "don't waste bits".  
> **username_0**: @AndrejBauer, Yes, there so many suitable  representations for a computable irrational number of finite length that interact with the computational complexity of it, what is the standard for good represent? And for discrete problem, we just know good by feeling, but clear and rigorious standard. As for computable irrational computable number,like $\sqrt{2}$,  we may have a computable sequence of integers as  coefficients of it's continued fraction, or a representation by program with a Kolmogorov complexity or something related to KC, which one is the best? [to be continued]  
> **username_0**: And, by representation with KC, we have a universal standard or uniform representation for the input, but program with length of KC is not computable, with a variant of KC, our choice is somehow arbitary, and makes the comparison between reals meaningless or too unstable.  
> **username_3**: _the BSS model seems suitable for computational geometry_ — See [my answer to a related question](http://cstheory.stackexchange.com/a/2124/111).  The Real RAM model used by computational geometers predates Blum, Shub, and Smale by almost a decade.  
> **username_0**: @JɛﬀE, Thank you for your comment, it'd rather be an answer.  

---

## 2 answers

### Answer by username_2 on 2014-11-20. Score: 13

I am not exactly sure what the question is here, but I can try to say a bit to clean up possible misunderstandings.

First of all, if we are talking about complexity of a map $f : \mathbb{R} \to \mathbb{R}$, it makes *no sense* to ask "What is a good representation for $\sqrt{2}$?" Instead, you have to ask "What is a good representation for *all* inputs of $f$?". Compare the situation with an easier one in discrete math: when you discuss an algorithm which takes a graph as an input, you do not ask "Should we represent the Petersen graph as as an adjancency list or as a binary matrix?" but instead you automatically think of a *uniform* representation which will work for all graphs.

Another word of warning. By changing the representation of the input data we can *always* make any problem (including a non-computable one) trivially computable: in order to make $f : A \to B$ computable, represent the elements of $A$ as pairs $(a, f(a))$. Then you can "compute" $f$ by the second projection. This shows that we need clear criteria of what it means to represent data.

I have written on several occasions about what it takes to represent the elements of $\mathbb{R}$. The answer depends on what *structure* of $\mathbb{R}$ you are trying to capture. If you are trying to capture no structure, then you can represent all reals with the empty list, for example. A reasonable list of conditions for a representation of $\mathbb{R}$ is that it needs to be such that:

1. The arithmetical operations $+$, $\times$, $-$, $/$ are computable, as well as the absolute value $|{-}|$.
2. There is a program which takes (the representation of) a real $x$ and $k \in \mathbb{N}$ and outputs integers $p, q$ such that $|x - p/q| \leq 2^{-k}$, i.e., it is possible to compute arbitrarily good rational approximations.
3. There is a program which takes (representations of) reals $x$ and $y$ and terminates if, and only if, $x < y$, i.e, the strict order is semidecidable.
4. Given a sequence (of representations of) $(x\_n)\_n$ such that $|x\_{n+1} - x\_n| \leq 2^{-n}$ a representation for the limit $\lim\_n x\_n$ can be computed.

There are old theorems (see introduction to [this paper](http://www.jucs.org/jucs_16_18/canonical_effective_subalgebras_of) for references) which explain why these conditions are the correct one. These theorems also show that any two such representations of reals are computably isomorphic, that is, we can translate between them with programs. This sets up some criteria for correctness that throw out faulty ideas.

For example, I hear people say things like "rational numbers can be represented by finite information, so let's use that for rational numbers, and the irrational numbers will have to be represented by infinite information". This sort of thing does not work because it breaks the fourth condition above (consider a limit of irrational numbers -- how will you tell that it is converging to a rational?).

Another example which the above conditions eliminate is the Blum-Shub-Smale model because in it you cannot compute limits of sequences. It is better to say that the BSS model works on a discrete ordered subfield of reals (generated by whatever parameters are present), not on the reals themselves.

Among the correct representations of reals some are more efficient than others, although this is a somewhat difficult topic to discuss because real numbers are infinite objects. Matthias Schröder [pointed out](http://homepages.inf.ed.ac.uk/als/Research/Others/schroeder-mlq04.pdf) that for a reasonable theory of complexity one has to pay attention to the topological properties of the representation.

Finally, *how* should we measure the complexity of a map $f : \mathbb{R} \to \mathbb{R}$, assuming we have a good representation of $\mathbb{R}$? Because $x \in \mathbb{R}$ is represented by a function, or an infinite stream of information, or some such, we should be using one of the [higher-type notions of complexity](http://www.cis.syr.edu/~royer/bib2.html). Which one probably depends on the representation you are using.

The BSS model is a also a reasonable circuit complexity model in which we count arithmetical operations. It's just good to keep in mind that this model is not about real numbers, but about something else.

> **Comments:**
> **username_0**: Thank you very much for your answer, and so many references. I feel uncomfortable about some notions of computational complexity, let me read the reference and think about for a time, and give an example, if I can find suitable one to explain why I am so uncomfortable( this sounds funny, But my experience tell me if I feel uncomfortable, there must be something singular)  
> **username_4**: In my experience, feeling uncomfortable about new knowledge is a good sign, and usually it is a prerequisite for enlightenment.  

---

### Answer by username_5 on 2014-11-23. Score: 3

Another model possibly to explore, is that of the Feasible RAM model. This is a modified real RAM model for Real computation, Feasible RAM, or a modified RAM model which uses both the discrete, and real valued arithmetic operations. This model allows for real, and discrete operations, and the Turing model, is interchangeable with it. The Feasible RAM model has precision defined with uncertainty, which means that $<\_{k}$ allows comparisons of real numbers only up to a variable uncertainty 1/(k+1). This allows for approximative computations. Also, as Vasco Brattkaa and Peter Hertlingb state in [Feasible Real Random Access Machines](http://www.sciencedirect.com/science/article/pii/S0885064X98904885) - the models of Turing, and that of Feasible Real RAMs, are related. All functions computable on a Turing machine in time $O(t)$ are computable on a RAM in time $O(t)$, and in the obverse case there some overhead for the Turing machine that computes the function(if real RAM computes the function in $O(t)$ the TM computes the function in $O(t^{2}log(t)log(log(t)))$. As pointed out topological considerations are useful, one doesn't know if there is any topological context developed for this model of computation that allows for real computations -which has uncertainty in precision.

> **Comments:**
> **username_0**: Could you give some reference for the feasible RAM model?  
> **username_5**: See above in the area, "... this reference states ..." has a link to the article.  
> **username_2**: Thanks for pointing out to the Brattka & Hertling work, I was going to mention it by then I forgot. I would just like to point out that the Feasible RAM model does not include any higher-order functions, in particular it cannot compute the limit of a (rapid) Cauchy sequence, so I would not count it as implementing "the reals" precisely. It can compute one limit "on the top level", so to speak (see the part of the paper where they speak about rational approximations of functions).  

---

