# Computable Numbers and Cantor's Diagonal Method

We were given the following problem in our university:

We will call $$x \in (0; 1)$$ computable iff there exists an algorithm (e.g. a programme in Python) which would compute the $$n^{th}$$ digit of $$x$$ (given arbitrary $$n$$.)

1. Prove the set of computable numbers is countable
2. Let's enumerate all the computable numbers and the algorithms which generate them (let algorithms be $$T_1, T_2, ...$$) Then we implement an algorithm such that $$A(n) \neq T_n(n)$$. So, we got a computable number which is not in the list. But we can't state that the set of computable numbers is uncountable due to point 1. Explain this paradox.

Here's my solution:

1. Number of programmes is countable $$\blacksquare$$.
2. So, why could Cantor's method work? It would work if this weird $$A(n)$$ algorithm was actually implementable (our algorithm theory hasn't started yet, so I am just thinking of all these ~algorithms~ as Python programmes, as suggested in the statement). But, given point 1, I suppose we rather have proven that $$A(n)$$ is not implementable. [Alternatively, we can, once again, use 1 to prove the existence of bijection from the computable numbers to $$\mathbb Q$$. Disproving the incorrect application of the diagonal method to $$\mathbb Q$$ is a calculus problem, not particularly hard, so I do not want to overburden the post with it.]

Point 2 seems too shaky (probably due to the excessive use of point 1.)

So, did I get this right? If not, I would appreciate a hint towards the correct solution.

• You're absolutely on the right track - in fact, $A$ is not algorithmically implementable. However, you can say more about this; can you pin down exactly why $A$ is more complicated than it may at first appear? Think about the sentence "Let's enumerate all the computable numbers and the algorithms which generate them (let algorithms be $T_1,T_2,$...)" Jan 21 at 20:00
• @NoahSchweber I guess we cannot have a formula $S(i, n) = T_i(n)$ to do smth like $A(n) := 9 - S(n, n)$, so we would have to either store all the $T_1, T_2, ...$ in memory (immediately contradicting the Python intuition from the statement) or somehow guessing whether $T(n, n)$ returns, let's say, $1$ and putting $0$ if it does or $1$ if it does not. The second option appears to be way more shady to immediately cast it away without the point 1. [And as I've mentioned in square brackets, there's no rational number for $A$ :D]. Or is there better reasoning? Jan 21 at 20:07

It looks like you are on the right track. However, some of your statements are not clear. For example, I do not see the relevance of "the existence of bijection from the computable numbers to $$\Bbb Q$$".
The moral here is that a set is countable does not imply it is a computably-enumerable set. There is no paradox here. In fact, almost all subsets of $$\Bbb N$$ is not computably enumerable although all of them are countable sets. The number of Python programs are countable. Since a computably-enumerable set can be produced by a python program, the number of computably-enumerable sets are countable. However, the number of subsets of $$\Bbb N$$ is uncountable.