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 '13 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 '13 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 '13 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 '13 at 15:31
  • 4
    $\begingroup$ Please, please please say undecidability from now on. $\endgroup$
    – Vijay D
    Aug 10 '13 at 5:04

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, privacy policy and cookie policy

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