4 ms·

You are incorrect, in fact the Halting Problem is RE-complete, https://en.m.wikipedia.org/wiki/RE_(complexity) https://en.m.wikipedia.org/wiki/RE_(complexity)

• lisper 6y ago
  I don't see how your citation supports your position: "In computability theory and computational complexity theory, RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time." But the halting problem requires you to produce a YES OR NO answer within a finite time. That's the whole point.
  • mlthoughts2018 6y ago
    It’s right there: > “ Examples of RE-complete problems: > Halting problem: Whether a program given a finite input finishes running or will run forever.”
    • lisper 6y ago
      Ah. Well, that's just a mistake. It's a misleading use of the term "the halting problem." There is a problem which is a variant of the halting problem which is RE-complete, namely, the problem of determining whether a given program halts. But that is not THE Halting problem, it is merely a halting problem. THE Halting Problem is the problem of determining whether a program halts OR DOES NOT HALT, and THAT problem is famously not in RE.
      • throwhoward 6y ago
        It's not just not in RE, it's undecidable https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem Ie equivalent to Godel first incompleteness them (but we all know this because we've all read super)
      • krackers 6y ago
        >the problem of determining whether a given program halts. But that is not the Halting problem Huh? That is indeed the halting problem. More formally "given some turing machine H and an input x, decide whether H halts on x." But it is of course trivially semi-decidable. >determining whether a program halts or does not halt That is equivalent to the formulation mentioned above, since if we had a decider W for the halting problem then H(x) halts iff W(H, x) accepts and halts, and H(x) does not halt iff W(H, x) rejects and halts. I think your confusion stems from the fact that if we had a decider for the halting problem, then the halting problem would be in R. But the fact that the halting problem is undecidable (i.e. not in R) means it is in RE but not co-RE.
        • lisper 6y ago
          You're right. I stand corrected. Unfortunately, it is too late for me to go back and edit my erroneous comment.