# Does this paradox prove that the halting problem is undecidable?

A real number is said to be computable if a finite, terminating algorithm can compute it to arbitrary precision. Since algorithms are countable (for example, one may list all possible c programs in lexicographical order), so are computable numbers.

Then, one may build the list of all computable numbers, in the order they appear in the list of all algorithms. One may now extract a new number from this list, much like in Cantor's diagonal argument, by having it's $$n$$th digit to be different from the $$n$$th digit of the $$n$$th computable number (e.g., $$x\mapsto (x+1)\;mod\;10$$). This number will not be computable as it is different from every number in the list. Yet, it looks like we have an algorithm to find it.

What seems to be the trick here, is that no algorithm for building the list of computable numbers exists, as it should have to decide whether a given algorithm does not halt in order to skip it. To avoid a contraddiction, the halting problem must be undecidable.

Can this paradox be turned into an actual formal proof, or some fine details of formal logic get in the way, making the argument flawed?

• Consider only $x \in [0,1)$ and its base-10 expansion. As you create the list, you only need consider algorithms that, at list item $n$, output a string of at least $n$ digits. We don't care if they halt after step $n$, or if (as we hope) they go on forever computing digits (and if it goes forever, we do not care if it computes a previously computed number). Your list still contains all computable numbers (with redundancies) and it seems the Cantor argument still gets one not on the list! Commented Aug 25, 2023 at 20:15
• There is always the problem: 0.0999... = 0.1000..., so you cannot say two numbers are different just because every digit is different. But other than that the proof is correct. Commented Aug 25, 2023 at 20:15
• @Michael Your argument is not valid because even though a program does not halt, it doesn't mean it will produce infinitely many digits. So when we encounter a program that takes a long time to compute the 3rd digit, we can never say for sure whether we should wait or we should declare the decimal had ended there. Thus the diagonal number is no longer computable, breaking the chain of logic. Commented Aug 25, 2023 at 20:19
• Ah, there is also the slight problem that actually digits of a computable number may not be computable. For example if my algorithm says it is one whatever precision I want it to compute, I never know whether it starts with 1.000... or 0.999... Because it might be that for the next precision that I query it will turn out to be less than one. You can fix this by using 9-adic numbers that has 10 digits 0–9, because this "overspill" gives you room to correct. Commented Aug 25, 2023 at 20:25

It is correct that you can effectively list all "algorithms" (or better, all partial computable functions $$\mathbb{N}\to\mathbb{N}$$), but this does not imply that you can list all the computable (real) numbers. For the sake of this argument (and to ignore problems like multiple representations of reals and such), let us forget about numbers and let's talk about infinite strings of natural numbers. Your argument is essentially showing that you cannot computably list all the computable infinite strings, or, if prefer, you cannot computably list all and only the total computable functions $$\mathbb{N}\to\mathbb{N}$$.
As mentioned in the comments, the problem is that you can't (computably) tell if a machine is never going to halt or if it is just needs more time. Imagine for example that your $$n$$-th program does not seem to converge on the $$n$$-th digit. Your algorithm for computing the diagonal string should, in finite time, commit to choosing the $$n$$-th digit for the diagonal string. After that stage, the $$n$$-th algorithm can choose to produce exactly the digit that your algorithm picked.
To make it even more precise, let $$(\varphi_e)_{e\in\mathbb{N}}$$ be a computable list of all partial computable functions. Let $$f:\subset \mathbb{N}\to\mathbb{N}$$ be the partial computable function defined as $$f(e):=\varphi_e(e)+1$$. Clearly $$f$$ is partial (e.g. take $$e$$ be the index of the algorithm that never converges on any input). If there were a computable enumeration $$(\varphi_{e_i})_{i\in\mathbb{N}}$$ of all total computable functions (i.e. if the map $$g(i):=e_i$$ were computable), then $$f$$ restricted to $$\{e_i : i\in\mathbb{N}\}$$ would be total. In particular, $$f\circ g$$ would be a total computable function not listed in $$(\varphi_{e_i})_{i\in\mathbb{N}}$$.
Observe that knowing whether a program halts on a given input is not enough to tell whether a function is total or not (i.e. if it halts on every input). However, you argument can certainly be adapted to show that the halting problem is not computable: if it were computable you could effectively find an enumeration $$(\psi_j)_{j\in\mathbb{N}}$$ of all problems that halt on their index. It would be enough to start from $$(\varphi_e)_{e\in\mathbb{N}}$$ and then, for each $$e$$, check whether $$\varphi_e(e)$$ halts. Then modify the definition of $$f$$ saying that $$f(e):=0$$ if $$\varphi_e(e)$$ does not halt. Such $$f$$ would be total and computable, hence it would halt on its index, but is not enumerated in $$(\psi_j)_{j\in\mathbb{N}}$$, contradiction.