Since both proofs make use of the diagonal argument, I’m wondering whether there is an obscure link between the existence of uncountable infinite sets and the undecidability of the halting problem. Would the halting problem be decidable if all sets were countable?

  • 10
    $\begingroup$ Yes, the diagonal argument! $\endgroup$ Aug 7, 2013 at 14:51
  • 1
    $\begingroup$ @MCH My thought was that there is maybe a different characterization besides the diagonal argument that connects both. This question is maybe too blurry for SE. $\endgroup$
    – Lenar Hoyt
    Aug 7, 2013 at 14:59
  • 4
    $\begingroup$ This may be a partial link: clearly, the set of all languages over a given alphabet is uncountable. However, the set of all Turing machines is countable. This directly implies the existence of undecidable problems. However, this reasoning implies nothing about the halting problem. $\endgroup$
    – 042
    Aug 7, 2013 at 15:31
  • 9
    $\begingroup$ There are certainly set-theoretic models of ZFC where all sets are countable (although not within the model), but the halting problem is always undecideable. See this MathOverflow question. $\endgroup$ Aug 7, 2013 at 15:31
  • 4
    $\begingroup$ Please, please please say undecidability from now on. $\endgroup$
    – Vijay D
    Aug 10, 2013 at 5:04

1 Answer 1


It's not a hidden link but one that has been made explicit using the language of category theory and also a very natural question to ask and study. There is a fair bit of material on the subject.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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