patternMinor
Why are computable numbers (in Turing's sense) enumerable?
Viewed 0 times
whycomputablearenumbersenumerablesenseturing
Problem
Why are computable numbers (in Turing's sense) enumerable?
It must be very obvious, but I'm currently just not seeing it.
It must be very obvious, but I'm currently just not seeing it.
Solution
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.
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.
Context
StackExchange Computer Science Q#7654, answer score: 5
Revisions (0)
No revisions yet.