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



How to define the input of computable function or Turing machine over real numbers
A good place to start learning about different representations of reals and their computability- and complexity-theoretic consequences is Weihrauch's book *Computable Analysis*.


