3
$\begingroup$

Upon applying the Cantor diagonal argument to the enumerated list of all computable numbers, we produce a number not in it, but seems to be computable too, and that seems paradoxical.

For clarity, let me state the argument formally. It suffices to consider the interval [0,1] only. Consider $0 \leq a \leq 1$, and let it's decimal representation be found as $$ a =\sum_{n=1}^\infty 10^{-n} a^{(n)} $$ We say that $a$ is computable, if there is a Turing machine $T_a$ which receives $n$ and outputs $a^{(n)}$ in finite time, i.e., it always halts.

Let $A$ be the set of all computable numbers. A moment's reflection shows that $A$ is countably many. For example, we can implement $T_a$ in (say) Python, always choosing the program with the shortest string length, and we sort $T_a$ by their program according to the ASCII characters' dictionary order. If two programs, which both implement $T_a$, have the same string length, choose the one with foremost dictionary order. This gives a sorting function of $A$.

Let $A$ be enumerated with $a_1, a_2, a_3 \dotsc$. Now, construct a number $b$ so that: $$ b =\sum_{n=1}^\infty 10^{-n} b^{(n)} \\ b^{(n)} =\begin{cases} 4,\quad a_n^{(n)} =3 \\ 3,\quad \rm{otherwise} \end{cases} $$ We see $b \notin A$. Moreover, $b^{(n)}$ is obtained within finite time, since we only need to know $a_n^{(n)}$'s value. Thus $b \in A$, but $b \neq a_n$ for all $n =1,2,3, \dotsc$, a contradiction.

This post is related, but I don't think it's a duplicate. The post applies the diagonal argument on the reals, rather than the computable numbers.

$\endgroup$
  • 1
    $\begingroup$ How is your Python program going to determine which Turing machines always halt? (In fact, it can’t.) $\endgroup$ – Mitchell Spector Mar 13 at 17:15
  • $\begingroup$ Perhaps I am a bit ignorant but I fail to see how $a$ is a computable number from your definition. $\endgroup$ – Matthew Liu Mar 13 at 17:25
  • $\begingroup$ @MitchellSpector The program listed to produce $a_n$'s are chosen to always halt, so I think the definition of $b$ doesn't need to worry about the halting problem of existing $a_n$'s. $\endgroup$ – Violapterin Mar 13 at 17:28
  • 2
    $\begingroup$ There is no way for a program to look at a Turing machine (or at a string that represents a Turing machine) and determine if it always halts. Your contradiction essentially proves that. $\endgroup$ – Mitchell Spector Mar 13 at 17:32
  • 1
    $\begingroup$ My bad, misread your notation. $\endgroup$ – Matthew Liu Mar 13 at 17:38
4
$\begingroup$

seems to be computable too

It's not, though. To run your argument you need to begin with a computable list of all the computable reals. But this doesn't exist.

We do of course have a computable list of all the Turing machines, but not every Turing machine describes a real number - to tell whether a Turing machine describes a real number, we need to know whether it halts on every input. But the set of (indices of) Turing machines which halt on all inputs is noncomputable (in fact, very noncomputable - strictly more complicated than the halting problem itself, which focuses on a single specific input!).

(Incidentally, the context of real numbers just adds a bit of unnecessary "noise" to the problem (and actually, this is true in Cantor's original argument as well); it's easier at first to just think about infinite sequences of $0$s and $1$s.)


Put another way:

The computable reals are "computably uncountable."

Similarly, the polynomial-time computable reals are "polynomial-time uncountable" (but they are "computably countable"). Cantor's argument shows that the "simply describable reals" are never "simply describably countable," for any reasonable meaning of "simply describable;" the full result - actual uncountability of the actual reals - is what you get when you take "simply describable" to just mean "in existence."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.