# Is there computable function to compute each computable real number?

Recall that a computable real number is one which can be calculated to any precision, like $\pi$ or $e$. It does not matter that these numbers are irrational, computability is about being able to compute rational approximations.

Is there a computable function which outputs an (infinite) sequence of Turing machines, each of which computes a real number, and such that all real numbers are so included?

• I don't think this question is suitable here, it seems to be mainly confusion about basic definitions. A real number is often represented by a function (e.g. a function over natural numbers). The computability of infinite objects like real numbers are usually defined using such representations of real numbers. A computable real number is also given by a finite algorithm. $\sqrt{2}$ and $\sqrt{x}|_{x=2}$ are the same object. – Kaveh Aug 9 '13 at 7:35
• I have edited the question so that it makes sense. If this is not what @Dims is asking, then he should try harder. – Andrej Bauer Aug 9 '13 at 10:49

A real number $x$ is said to be computable if there a Turing machine, which upon input $n \in \mathbb{N}$ outputs a pair of numbers $a, b \in \mathbb{N}$ such that $|x - a/b| < 2^{-n}$. That is, there is a machine that computes arbitrarily precise rational approximations of $x$.
• perhaps in summary: the set of computable real numbers is countable, but not recursive enumerable (reduction from $A_{HALT}$ the problem of deciding if a TM halts on all inputs). – Marzio De Biasi Aug 9 '13 at 14:51
• Not quite, because recursive enumeration only applies to natural numbers. So slightly more precise would be: there is no recursively enumerable set of codes of computable reals such that each computable real has a code in it. It is better to introduce the notion of a numbered set and then: "There is no surjective computable map from $\mathbb{N}$ onto the numbered set of computable reals." – Andrej Bauer Aug 9 '13 at 18:05