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

canimplement 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 Aug 13 '14 at 7:505more comments