# 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? – tohecz 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

## migrated from cstheory.stackexchange.comDec 31 '12 at 3:21

Computable number is a number whose binary expansion is computable by a Turing machine (and some additional conditions). Since Turing machines are maps $\mathfrak t:\mathcal S\times \mathcal A\mapsto \mathcal S\times \mathcal A\times \{-1,0,1\}$, for finite $\mathcal S$, $\mathcal A$, they are obviously enumerable. Therefore, all computable numbers are enumerable.

-

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.

-