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.

 

[.Scott]

That's a good point.
Cantor's diagonal argument is not iron-clad. Bertrand Russell complained about it in Principia Mathematica, as described here.

When the algorithm for finding a "Cantor solution" is implemented for only a specified precision, what it returns is only a promise that such a solution can be found within the specified precision of that returned value. However, since the actual full solution can only be found after reaching the end of an $\aleph_0$ list, this is a highly dubious promise.

To illustrate how dubious that is, consider this: Once a Cantor solution is found, then every digit after that "last" digit can be anything - and each new choice of "anything" would be new to that original $\aleph_0$ list. Thus you would be adding $\aleph_1$ new entries to your $\aleph_0$ list. But, of course there is no "last digit" so the promised solution is by definition, ill-defined.

 

[Warp]

Some possible solutions to the paradox come to mind (I have not looked any of this up online, even though I'm sure I'm not the first one to think about this exact problem):

• Somehow, the set of computable numbers is actually uncountable even though its definition makes it sound like it isn't.
• Cantor's diagonal argument is flawed and actually doesn't prove that a set is uncountable (and this very paradox would be the proof of it, as assuming it works leads to a contradiction.)
• It's not possible to compute the complete (indexable) list of computable numbers, making the hypothetical newly formed number actually uncomputable.
• The entire concept of "computable number" is ill-formed, self-contradictory and impossible, and thus the set doesn't exist at all, making this entire exercise moot because it's based on the false premise that such a set exists.

 

[Demystifier]

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.

No, that's not the definition of the computable number. Sure, all computable numbers have this property, but the converse is not true: it is not true that all numbers with that property are computable. In fact, by your diagonal argument you proved just that.

If you take the definition from wikipedia, don't use the informal "definition" from the introduction. Instead, take the formal definition given later. The formal definition is based on the more general notion of computable function. The computable function is defined
https://en.wikipedia.org/wiki/Computable_function
as an algorithm that just computes the value of the function, not as an algorithm that computes it to arbitrary precision.