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.

 

[JeffJo]

Here is my rendition of Cantor's Diagonalization Argument. It is really a different phrasing of the one in Wikipedia.

1. A "Cantor String" is an infinite string of 0's and 1's. That is, a function c:N-->{0,1}.
   1. It describes a subset of N, where a 1 indicates membership in the subset.
2. Let C be the set of all Cantor Strings.
   1. It is the power set of N, which exists by axiom.
3. Let s be any function s:N-->C. Let S be the range of s, a subset of S.
   1. So s(n) is the nth Cantor String by this counting, and s(n)(m) is the mth character in that Cantor String.
4. Define a new function d:N-->??? (that is, we do not know the codomain yet) such that d(n) = 1-s(n)(n).
   1. This d is a member of C because it maps N to {0,1}.
   2. This d is not a member of S.
5. Conclusion: S is a strict subset of C, so there is no surjection s:N-->C.

Two comments: this does not use real numbers, and it is not a proof by contradiction. It is, however, an accurate rendition of what Cantor. He didn't use real numbers, and did not use a proof by contradiction the way you think he did. (The conclusion was unnecessarily framed as one: If C=S, d would both be in, and not be in, C. It was unnecessary because 4.2 already proved this.)

Where your suggestion fails, is step 4.1. You have not proven that the diagonal number you get is a computable number.

 

[SSequence]

Let me specifically focus on functions from $\mathbb{N}$ to $\{0,1\}$ [instead of computable number] and different reditions of a method similar to what you described in the OP. I will describe the various conclusions we can draw from them.

(1) Firstly, we have an (easily understandable) 1-1 correspondence between all programs (any computational model) and natural numbers. Here is where the first main issue comes up. A program can be interpreted in many different ways. However, for this specific post, let's think of every program as computing a partial function [a function that may or may not be total] from $\mathbb{N}$ to $\{0,1\}$. What it means is that there might be some inputs $x$ for which the program never halts and we declare our function to be undefined for those values. Usually this is assigned another special symbol (the most common symbol is the upward arrow $\uparrow$).

The term diagonalization can mean various things now. Let's consider various ways to think about it.

(2) One way to "diagonalize" is to define the following function $f:\mathbb{N} \rightarrow \{0,1\}$:
$f(x)=1$ --- if the program with index $x$ halts and returns $0$ as output
$f(x)=0$ --- if the program with index $x$ halts and returns $1$ as output
$f(x)=\uparrow$ --- if the program with index $x$ doesn't halt

Note that the above function is not total. It can be shown that the above function $f$ is a partial computable function. In other words, there exists some program that computes the above function $f$.

(3) Another way to "diagonalize" is to define the following function $g:\mathbb{N} \rightarrow \{0,1\}$:
$g(x)=1$ --- if the program with index $x$ halts and returns $0$ as output
$g(x)=0$ --- if the program with index $x$ halts and returns $1$ as output
$g(x)=0$ --- if the program with index $x$ doesn't halt

Note that the above function is total. This above function $g$ is not computed by any program.

(4) One other way to "diagonalize" is to consider all programs that halt for all their inputs and then diagonalize over them [just like we would diagonalize over any collection of total functions]. The resulting function will be total but again it won't be computed by any program.

===========================

I remember reading somewhere that when the notion of computable functions was discovered, Kleene thought about the description of a non-computable function by diagonalizing over them. It was probably similar to functions described in either point-(3) or point-(4).

 

[SSequence]

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?

Here is the answer to your specific question. With each partial computable function $f:\mathbb{N} \rightarrow \{0,1\}$ we first need a way to associate with it a real number (in decimal form) in the interval [0,1]. Suppose we denote the set $A$ as the set of all partial computable functions from $\mathbb{N}$ to $\{0,1\}$. Then this association would be a total function from $A$ to [0,1].

So suppose we are given an arbitrary partial computable function $f:\mathbb{N} \rightarrow \{0,1\}$. The most "obvious" way to associate it to a real number seems to be to define $m$ as the smallest number such that $f(m)=\uparrow$. If such a number $m$ does exist then we define our real number associated with $f$ as (this will actually be a rational number):
$0\,.\, f(0) \, f(1) \, f(2) \, f(3) \, ....... \, f(m-1)$
If such a number $m$ doesn't exist then we define our real number associated with $f$ to be:
$0\,.\, f(0) \, f(1) \, f(2) \, f(3) \, ....... \, f(i) \, f(i+1) \, ........$


Now what is being suggested in OP is that for the $n$-th number on the list we look at its $n$-th digit and change it (as done in the usual diagonalization argument). However, the problem here is the following [with the association of partial computable functions and real numbers mentioned in previous paragraph]:
How do we determine the $n$-th digit generally (in an algorithmic way)?

For an arbitrary $n \in \mathbb{N}$, determining the $n$-th digit here will not give us a computable function. That's because the function $F:\mathbb{N} \rightarrow \{0,1\}$ being suggested in OP goes as follows:
$F(x)=0$ --- if the program with index $x$ halts on all inputs $\leq x$ and returns $1$ on input $x$ itself
$F(x)=1$ --- if the program with index $x$ halts on all inputs $\leq x$ and returns $0$ on input $x$ itself
$F(x)=1$ --- if the program with index $x$ doesn't halt on atleast one input $\leq x$

Now this function $F$ is a total function. As I see, $F$ could shown to be non-computable using reducibility arguments similar to ones used quite a bit in computability theory. The argument would go somewhat like that if the function $F$ was computable then halting probelm would be computable too [hence we conclude $F$ to be non-computable].


P.S.
The kind of association between partial computable functions and real numbers that I mentioned would have lot of other issues too. People who have substantial familiarity with sub-branch known as computable analysis would be well-aware of it.

I also vaguely remember reading that other alternative definitions of real numbers (not based on decimal expansion) are sometimes preferred in computable analysis for reasons based on previous paragraph. But I should add that I don't have any knowledge of this myself so I can't say much about it.