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$.)

• Prove the set of computable numbers is countable

• 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:

• Number of programmes is countable $\blacksquare$.

• 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.

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$".

Hint 1.

As you might have suspected, it is not possible to computably enumerate all computable numbers, although the set of computable numbers is countable and it is possible to computably enumerate all Python programs.

Hint 2, which is almost the simple solution.

In fact, the application of Cantor's diagonal method as explained in the original problem shows that any computable enumeration of computable numbers will miss at least one computable number. Hence, it is not possible to computably enumerate all computable numbers.

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.

StackExchange Computer Science Q#148566, answer score: 2