Can every computable number be listed?

Question

Computable number is countable. Does this mean computable number can be listed one by one?

Answer 1

The answer depends on what you mean by "can be listed". In set theory, a set $S$ being countable means that there exists such a "list", or more specifically, a bijection $f:\mathbb{N} \rightarrow S$. However, just because such a bijection exists doesn't mean we can actually determine a specific, concrete, computable example of such an $f$. In the case of computable numbers, we know that such a bijection exists because there is a bijection $f: \mathbb{N} \rightarrow B$ where $B$ is the set of finite binary strings, and every computable number can be formed by running a universal Turing machine on this binary string as input. However, some of these binary strings $b \in B$ will not result in a computable number, because they might not ever halt: they might start a number, like 34.34... but then never give you a third digit and continue computing forever. (or they might produce nonsense output like $34.34.2.$) In abstract, we can define a bijection $g: \mathbb{N} \rightarrow C$, where $C$ is the set of computable numbers, by saying $g(1) = $ (the first computable number produced by such a $b$), $g(2)$ being the second computable number produced after the first, and so on inductively; these numbers must exist, because of the property of the natural numbers that every nonempty subset of $\mathbb{N}$ must have a first element. However, in practice we cannot say which binary strings $b$ will give rise to a computable number, because a Turing machine cannot solve the halting problem of telling which Turing machines halt. Depending on the specifics of the universal Turing machine you are using, you might be able to identify $g(1), g(2), g(3)$, say, by some ad-hoc process of elimination and case-by-case analysis of a large set of binary strings, but you won't be able to get very far.