If, given Turing machine T, "T halts" or "T doesn't halt" could be derived from axioms of ZFC, halting problem would be in R. As it isn't, there must exist a Turing machine for which truth or falsehood of halting is independent of ZFC.

I want to see it. Is such machine known?

  • $\begingroup$ What do you mean by "the halting problem would be in RE. As it isn't..." Usually, we show the set of halting programs is r.e. but it is not recursive. Functions are not called "r.e.", sets are, and the set of halting turing machines is definitely r.e. $\endgroup$ – Thomas Andrews Aug 3 '13 at 13:15

Let $T$ be the Turing machine which looks for a proof of a contradiction in ZFC. If ZFC is consistent, then whether or not $T$ halts will be independent of ZFC. (Indeed, if not, then this would contradict Gödel's incompleteness theorem!)

  • $\begingroup$ No, if ZFC is consistent, then $T$ won't halt. $\endgroup$ – Thomas Andrews Aug 3 '13 at 13:43
  • $\begingroup$ @ThomasAndrews, see Gödel's incompleteness theorems $\endgroup$ – Karolis Juodelė Aug 3 '13 at 13:45
  • 2
    $\begingroup$ @ThomasAndrews : Indeed if ZFC is consistent, then an algorithm doing an exhaustive search for a contradiction in ZFC will not halt. But that's not the same as saying you can prove in ZFC that it will not halt. Nor could you prove in ZFC that it will. So if ZFC is consistent, then it will not halt, and morevoer its halting or non-halting is independent of ZFC. $\endgroup$ – Michael Hardy Aug 7 '15 at 3:16
  • 1
    $\begingroup$ @PyRulez I think the deal is that, in ZFC+$\lnot$Con(ZFC), there are sets that the model thinks are finite but are actually infinite. The reason the model thinks they're finite is because a set is infinite iff there's an injection from it to a proper subset of itself, and injections are types of sets. So the model thinks the "finite" set is finite because the required injection isn't in the model. In any case, $\lnot$Con(ZFC) means there's a natural number that codes a proof of a contradiction in ZFC. There is, it's just that the "number" is infinitely big. $\endgroup$ – Akiva Weinberger Aug 7 '15 at 3:39
  • 1
    $\begingroup$ And the machine $T$ will halt, it just takes a "finite" (infinite) amount of time. $\endgroup$ – Akiva Weinberger Aug 7 '15 at 3:40

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.