2
$\begingroup$

Computation or computability over $\mathbb{N}$ can be extended to computation or computability over $\mathbb{R}$ or even computation or computability over $\mathbb{C}$.The following is a formal definition in An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul M.B. Vitányi:

Definition A real number $x = 0.x_1x_2 \dots$ is lower semicomputable if the set of rationals below $x$ is recursively enumerable. A number $-x$ is upper semicomputable if $x$ is lower semicomputable. A number $x$ is computable,equivalently, recursive, if it is both lower semicomputable and upper semicomputable

We may have other different definition that is closer to our intuition:

Definition if Given $r \in \mathbb{R}$, $\forall i\in \mathbb{N}$,there is Turing machine $\mathbf{M}$ that outputs $i$ bit of $r$,$r$ is computable real

By intuition,we know Universal Turing machine takes different time and space to output in the same amount of first bits(that is,any first $n$ bits) for different reals like natural numbers ,quotients,algebraic numbers and computable transcendental numbers,when we give an input to compute a real.for example,computation of $\sqrt{2}$ and $e$ may take different times and spaces(outputing same amount of first bits for $\sqrt{2}$ and $e$ ).

But we can give an algebraic equation as input to compute an algebraic number like $\sqrt{2}$ or an close form like $(1+\frac{1}{x})^x$ to compute $e$.Also we can compute $\sqrt{2}$ or $e$ with their continued fraction expansion as inputs.But different inputs to compute a same number like $e$ may take different time and space.

To measure the computational complexity of different reals,we have to give representation of reals,what representation of reals do we have to choose?Or how to define the input of computable function or Turing machine over real numbers to measure the computational complexity of different reals? Any answers or comments or reference are welcome

Improve this question
$\endgroup$
10
  • $\begingroup$ Here is a relevant post and answer mathoverflow.net/questions/99421/…, but they are only on algebraic number and equation. $\endgroup$
    – XL _At_Here_There
    Commented Aug 13, 2014 at 3:12
  • 3
    $\begingroup$ Regarding the question "what representation of reals do we have to choose", please read my answer at cstheory.stackexchange.com/a/16547/705 $\endgroup$
    – Andrej Bauer
    Commented Aug 13, 2014 at 7:26
  • $\begingroup$ @AndrejBauer,thank you.I have just browsed your answer to that post.The main point is :Turing Machine can not implement the axioms for what we call reals,so to ask for a suitable representation of reals is impossible? $\endgroup$
    – XL _At_Here_There
    Commented Aug 13, 2014 at 7:48
  • 1
    $\begingroup$ No, that is not the point. We can implement the reals, but it's a bit trickier than you'd expect. You cannot naively expect to implement equality as a boolean test, for instance, but you can implement inequality as a semidecidable test. So there are some surprises, and that's why people are so confused about computation over the reals. $\endgroup$
    – Andrej Bauer
    Commented Aug 13, 2014 at 7:50
  • 2
    $\begingroup$ I specifically preempted my comment with "regarding the question..." so as to make it clear I was not discussing complexity (although what I said still stands, except as you note, things get more complicated). Of course complexity is a very interesting issue. Some work has been done in Type Two Effectivity. Essentially, complexity on a space $X$ makes sense when each point of $X$ has compactly many representatives, see e.g. homepages.inf.ed.ac.uk/als/Research/Others/schroeder-mlq04.pdf $\endgroup$
    – Andrej Bauer
    Commented Aug 13, 2014 at 14:13

3 Answers 3

Reset to default
4
$\begingroup$

A good place to start learning about different representations of reals and their computability- and complexity-theoretic consequences is Weihrauch's book Computable Analysis.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you,Bjørn Kjos-Hanssen.It is the first time I know the book and such a domain,and it is relevant to the computational complexity of reals .But different representation of reals make the comparison of computational complexity of different reals meaningless.We have to choose a suitable one and prove it is suitable.I don't know which one is fit into those requiremen.Anyway,I have to read the book ahead. $\endgroup$
    – XL _At_Here_There
    Commented Aug 13, 2014 at 2:33
  • $\begingroup$ Some words from the book:Since we are not interested in some arbitrary computability theory on $\mathbb{R}$ we need a good justification for the choice of the Cauchy representation (or some equivalent one).In this section we explain why the Cauchy representation is topologically natural for the real line and why it is computationally natural We mention the concept of admissible representations and formulate the important continuity theorem for admissible representations. Finally we explain why several other representations of $\mathbb{R}$ cannot be natural. $\endgroup$
    – XL _At_Here_There
    Commented Aug 13, 2014 at 2:58
2
$\begingroup$

A good book on the complexity of real constants and functions is Ker-I Ko's "Computational Complexity of Real Functions", 1991.

Improve this answer
$\endgroup$
0
1
$\begingroup$

Another book, maybe not exactly what you want: Complexity and Real Computation, by Blum, Cucker, Shub, and Smale.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you ,none.Why not to change your name into a meaningful one? $\endgroup$
    – XL _At_Here_There
    Commented Aug 13, 2014 at 4:17
  • $\begingroup$ Some words from Complexity and Real Computation:Complexity classes over a ring $R$ are classes of problems categorized according to their solvability with respect to a given machine model and prescribed resource restrictions. We have seen various such classifications in the preceding chapters. In this chapter we show that a number of classes can be characterized in terms of the "complexity" of their descriptions. This provides machine-independent characterizations of important complexity classes and sheds some light on their comparison. $\endgroup$
    – XL _At_Here_There
    Commented Aug 13, 2014 at 4:38

You must log in to answer this question.