<p>There is a real question behind the confusion.</p>

<p>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| &lt; 2^{-n}$. That is, there is a machine that computes arbitrarily precise rational approximations of $x$.</p>

<p>We can ask whether there is a machine that outputs an infinite list of machines, such that each of the listed machines computes a real number, and all computable real numbers are so included. That would be the way to make sense of the question.</p>

<p>The answer is negative. There is no such machine. The proof is essentially the diagonalization argument that show that a sequence of reals cannot exhaust the set of reals, except it is modified to work for computable reals and computable sequences.</p>

CC BY-SA 3.0
2013-08-09T14:51:40.787Z
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
CC BY-SA 3.0
2013-08-09T18:05:53.543Z
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
CC BY-SA 3.0
2013-08-09T23:55:20.530Z
You're right (I wrote the set of computable real numbers is not r.e., but I was thinking about the set of the TMs that compute their approximations).
Marzio De Biasi
CC BY-SA 3.0
2013-08-10T07:34:21.127Z
You were thinking about the set of numbers that encode TMs that compute approximations to real numbers, no doubt.
Andrej Bauer
CC BY-SA 3.0
2013-08-09T10:46:34.477Z
2013-08-09T10:46:34.477Z
Andrej Bauer
<p>Recall that a <em>computable real number</em> 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.</p>

<p>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?</p>

CC BY-SA 3.0
2013-08-09T07:35:54.440Z
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
CC BY-SA 3.0
2013-08-09T10:49:52.160Z
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
CC BY-SA 4.0
2024-02-02T17:49:52.873Z
"*an (infinite) sequence of Turing machines, each of which computes a real number, and such that all real numbers are so included*"  Note that this is not possible simply because any sequence is only countably infinite, while the set of reals is uncountable.  (As far as I can tell, OP is not asking "such that all *computable* real numbers are included"...)
Neal Young
<computability>
Is there computable function to compute each computable real number?
Dims
# Is there computable function to compute each computable real number?

(Asked by: username_0 on 2013-08-08)

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?

**Tags:** computability

> **Comments:**
> **username_1**: 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.  
> **username_2**: I have edited the question so that it makes sense. If this is not what @username_0 is asking, then he should try harder.  
> **username_3**: "*an (infinite) sequence of Turing machines, each of which computes a real number, and such that all real numbers are so included*"  Note that this is not possible simply because any sequence is only countably infinite, while the set of reals is uncountable.  (As far as I can tell, OP is not asking "such that all *computable* real numbers are included"...)  

---

## 1 answers

### Answer by username_2 on 2013-08-09. Score: 8

There is a real question behind the confusion.

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$.

We can ask whether there is a machine that outputs an infinite list of machines, such that each of the listed machines computes a real number, and all computable real numbers are so included. That would be the way to make sense of the question.

The answer is negative. There is no such machine. The proof is essentially the diagonalization argument that show that a sequence of reals cannot exhaust the set of reals, except it is modified to work for computable reals and computable sequences.

> **Comments:**
> **username_4**: 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).  
> **username_2**: 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."  
> **username_4**: You're right (I wrote the set of computable real numbers is not r.e., but I was thinking about the set of the TMs that compute their approximations).  
> **username_2**: You were thinking about the set of numbers that encode TMs that compute approximations to real numbers, no doubt.  

---

