0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kaveh Aug 9 '13 at 7:35
  • 3
    $\begingroup$ I have edited the question so that it makes sense. If this is not what @Dims is asking, then he should try harder. $\endgroup$ – Andrej Bauer Aug 9 '13 at 10:49
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Marzio De Biasi Aug 9 '13 at 14:51
  • $\begingroup$ 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." $\endgroup$ – Andrej Bauer Aug 9 '13 at 18:05
  • $\begingroup$ 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). $\endgroup$ – Marzio De Biasi Aug 9 '13 at 23:55
  • $\begingroup$ You were thinking about the set of numbers that encode TMs that compute approximations to real numbers, no doubt. $\endgroup$ – Andrej Bauer Aug 10 '13 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.