The countability paradox of computable numbers

[Warp]

Famously, the set of computable numbers is countable. That's pretty much a result of their definition: The decimal expansion of a computable number can be generated to any arbitrary length by a finite algorithm. And since the set of all possible finite algorithms is countable, so is the set of computable numbers.

However, we can adapt Cantor's diagonal argument to make that paradoxical:

Since the set of computable numbers is countable, there's a 1-to-1 relationships between them and the natural numbers. Which means you can list all the computable numbers. Apply the diagonal argument:

Take the complete list of (the decimal expansions of) computable numbers, and go through the digits diagonal and generate a number that differs from each one of them. Now we have a number that's not on the list. But this number is computable! We just gave the algorithm to compute it to arbitrary precision!

Thus, the list was not complete, as we could generate a new computable number not in the list.

So, is the set of computable numbers countable or not?

 

[.Scott]

Famously, the set of computable numbers is countable. ...
However, we can adapt Cantor's diagonal argument to make that paradoxical:

Since the set of computable numbers is countable, there's a 1-to-1 relationships between them and the natural numbers. Which means you can list all the computable numbers. Apply the diagonal argument:

Take the complete list of (the decimal expansions of) computable numbers, and go through the digits diagonal and generate a number that differs from each one of them ...

A computable number must be the result of a "terminating algorithm". An algorithm that is required to examine each element in a list of cardinality $\aleph_0$ would be "non-terminating". Thus it's result might not be in the set of computable numbers.

 

[Warp]

A computable number must be the result of a "terminating algorithm". An algorithm that is required to examine each element in a list of cardinality $\aleph_0$ would be "non-terminating". Thus it's result might not be in the set of computable numbers.

It has to be a terminating algorithm that computes the number up to a given precision (which can be arbitrarily large). The Cantor's diagonal argument "algorithm" is exactly that: It can be used to compute the new number to an arbitrary given precision, and terminates when it has produced that many digits.

It can even run every algorithm that produces each one of the numbers in the list up to the required digit, which also makes them terminating.

Thus, it perfectly fits the definition of a computable number.