# Why are computable numbers (in Turing's sense) enumerable?

Why are computable numbers (in Turing's sense) enumerable? It must be very obvious, but I'm currently just not seeing it.

• Isn't it simply because all TMs are enumerable? – yo' Dec 30 '12 at 21:32
• That must be it. – Michiel Borkent Dec 30 '12 at 22:03
• Being enumerable means (by definition) that there is a Turing machine that halts with a yes-answer for every yes-instance. Since being computable means there is a Turing machine that halts with the correct answer for every input, it is easy to see that being computable implies it is enumerable (it is a sub case). – Jonas G. Drange Dec 31 '12 at 10:24
• I don't think this is the meaning of "computable" in this case. It is a construction problem, not a decision problem. – lvella Sep 5 '15 at 6:41

I'm assuming that your definition of a computable number is this: there is a Turing machine that on input $n$, halts with the $n$th bit of the number.

Suppose there were a recursive enumeration of Turing machines that produce computable numbers. You can use diagonalization to come up with a new computable number which isn't part of this recursive enumeration.

It is tempting to enumerate computable numbers by enumerating Turing machines, but not every Turing machine corresponds to a computable number, and in general deciding whether a Turing machine halts for all inputs (let alone output either 0 or 1) is not computable. It is, however, possible to enumerate all efficient computable numbers, say ones whose running time is polynomial, by using clocked Turing machines.

• So even though the cardinality of a set (in this case, the set of computable numbers) is not bigger then the cardinality of another set that is listable (the set of all TMs), it doesn't mean that the first set can be listed. – André Souza Lemos Sep 5 '15 at 18:58

If by enumerable, you mean that there is a bijection with the natural numbers (i.e., countable), then no, computable numbers are not enumerable.

Let's define the problem more precisely: a "Number-Printing Turing Machine (NPTM)" is a Turing Machine that, for every state transition, may print nothing, or may print any decimal digit, the minus sign, or the period. This is enough to print decimal representations of real numbers.

Lets define a computable real number as any real number that can be printed with arbitrarily long representation, given enough time, by a NPTM starting from an empty tape. Lets also say that a number is computed by a given NPTM iff it either halts after printing a well formed real number (in which case, the number has a finite decimal representation) or will, in a finite amount of time, print well formed number with a decimal point, and will ever increase the precision of the number by printing more digits, given ever more time.

This later condition needed because, if we have a machine that, for instance, prints an infinite sequence of some digit, say 1111111111111111111..., it cannot be said to be computing any real number, because real numbers only have infinite representation to the right side of the decimal period. On the other hand, if the machine prints 3.14 and then stops printing, but never halts, it cannot be said to be computing any real number simply because the precision of the number is not increasing, thus, this particular machine won't be constructing it further.

These are examples of NPTM that do computes some number. A NPTM that:

• prints 1, then halts. It computes number 1.
• prints 1.0, then halts. It also computes number 1.
• prints 1.0000000, and keeps printing zeros forever. This one also computes number 1.
• prints 3.14, then halts. It computes number 3.14.
• prints 3.14159, and goes on forever printing digits of $\pi$. This one computes number $\pi$.
• prints -42., and then halts. It computes number -42.

And these are examples of NPTM that do not compute any number. A NPTM that:

• prints 123123123 and then goes on printing the sequence 123 forever. Isn't computing a number because this infinite sequence does not represent any real number.
• prints 1.0.0 and then halts. Isn't because this finite sequence is not well formed.
• prints ....-..--- and then halts. Isn't because this is not a well formed real number either.
• never prints anything, but never halts either. There is no number being constructed.
• never prints anything and immediately halts. No number was constructed.
• prints 3.14, doesn't halt, but never prints anything else either. Isn't computing a number because its precision isn't increasing with time.

You've got the idea. Then we have two classes of NPTM: those that computes some real number, and those who don't.

The problem with finding some enumeration for the computable numbers is that, even if the NPTM are themselves countable, we can't have a procedure that separates one kind of NPTM from another.

Consider the definition of countable set: for a set $S$ to be countable, there must exist some bijective function $F: \mathbb{N} \rightarrow S$.

To "prove" that the computable numbers are countable, one might be tempted to define such a function from the counting of the NPTM (and this is what people often did, when they believe the computable numbers are countable). Something like this:

The NPTM are countable, so there is a bijective function $E_\text{NPTM}: \mathbb{N} -> \text{NPTM}$, thus we can go enumerating forever all NPTM that exists. So, to likewise enumerate all computable numbers, and precisely define the bijective function $E_\text{Computabe}: \mathbb{N} \rightarrow \text{Computable}$, one must simply enumerate all NPTM, but count only those that do compute some real number. But how do we know it computes some real number?

Well, we don't. Consider a machine that immediately prints 1.0, and then stops printing and goes on to try to solve an instance of the Post correspondence problem. If it solves the problem, it halts, then the machine just computed the number one. But that problem is undecidable, so it may never halt, and if it never halts, it never computes a real number. But we can't know if it will ever halt, because the Halting problem is also undecidable! So, since there is no way of knowing if this particular machine, and infinitely many other machines, either computes or not some real number, we can't build/define our bijective function in this way.

The naïve way to define the bijection fails, and it is not very difficult to prove that there is no way do it, whatsoever. As Yuval Filmus suggested, diagonalization can be used.

• You probably wanted to say "computable numbers are not enumerable" instead of "computable numbers are not countable". – IS4 Oct 29 '15 at 18:36