The computable numbers are countable. That's because the set of Turing machines is countable. Over a countable alphabet there are countably many TMs of length 1, countably many of length 2, etc.; and the union of countable sets is countable. QE Freaking D. — fishfry
?? Perhaps I should have been clearer from the beginning, but i took everyone's understanding for granted that a computable
number refers (in some way) to a computable
total function. Apologies if that is the case. For surely you appreciate that the computable
total functions
aren't countable?
The computable
total functions are a proper subset of the computable functions that also contain
partial functions. i.e. that do not halt on a given input.
It is true to say that the whole set of computable
functions is countable, for reasons you'e sketched. It is
not true to say that the set of computable
total functions are countable, for we cannot solve the halting problem. Hence the reason why we say the computable numbers are
sub-countable: the only way we could 'effectively' enumerate the computable numbers is to simulate every Turing machine and wait forever, meaning that any 'candidate enumeration' we construct of our computable numbers after waiting a finite time is also going to contain computable functions that aren't total and hence are not numbers.
For the constructivist, this "subcountability" is all 'that 'uncountability' means. It is simply means that we can never construct a total surjective function from the natural numbers onto the computable numbers. It doesn't mean in any literal sense that we have
more computable real numbers than natural numbers.
The sequence of n-th truncations of the binary expansion of Chaitin's number is a Cauchy sequence that does not converge to a computable real. End of story. Then you say, "Oh but that sequence isn't computable," and I say, "So freaking what?" and this goes on till I get tired of talking to yet another disingenuous faux-constructivist. — fishfry
We have to be careful there. We can run every Turing Machine and at any given time create a bar-chart of the ones which have halted, and this histogram comprises a sequence of computable functions whose limit isn't a computable function. To my understanding this sequence of functions isn't cauchy convergent, for we cannot construct a bound on the distance between successive histograms. Let's not forget that there are an infinite number of computer programs of every size.
Compare this situation to a computable total function f(n) representing the "values" of the Goldbach's Conjecture; Let's say that f(n) = 0 if every even number less than n is the sum of two primes, otherwise f(n)=1. Here we can also compute the individual digits in finite time. If GC is decidable, i.e. GC OR ~GC, then f(n) is Cauchy convergent to either 0 or 1. But if GC isn't decidable, then as with Chaitin's constant f(n) doesn't have a cauchy convergent limit, even though f(n) is a computable total function.
Therefore, in order to know that one has constructed a complete and ordered field of computable numbers, one must only use a set of provably Cauchy-convergent computable total functions, for which every cauchy-convergent sequence of these functions is also provably cauchy-convergent.