5
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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,$...)" $\endgroup$ Jan 21 at 20:00
  • $\begingroup$ @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? $\endgroup$ Jan 21 at 20:07

1 Answer 1

2
$\begingroup$

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.

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