Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question

migrated from cstheory.stackexchange.com Dec 31 '12 at 3:21

This question came from our site for theoretical computer scientists and researchers in related fields.

2  
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
2  
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

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.