0
$\begingroup$

The language A, that is all DTMS that run forever on input.

Would this not just be the HALT problem?

Therefore no reduction or proof is necessary, other then stating that?

ANSWER FOUND: I think i have it, if it was Turing Recognizable, then it would be possible to determine when HALT should reject and therefore HALT would be decidable. Since it is not-decidable, then A must be not Turing Recognizable.

$\endgroup$
  • $\begingroup$ Yes, it is just the complement of HALT_TM but without the descriptions that do not describe valid TMs. So why do you think would it not be Turing-recognizable? $\endgroup$ – Ryan Jul 27 '15 at 18:30
  • $\begingroup$ Since you found your answer, you should not leave it in a comment but either add it as another answer, or include it as an edit in the question. IMHO. $\endgroup$ – babou Jul 28 '15 at 12:20
2
$\begingroup$

This is not the halting problem, the halting problem is the set of TMs that do halt, the language $A$ is the set of TMs that don't halt. It's the complement of the halting problem.

You also seem to be mistaken in that the halting problem is recognizable, it's just not decidable.

$\endgroup$
  • $\begingroup$ Thank you! If I wanted to prove that it is not Turing Recognizable, would I have to do a reduction? $\endgroup$ – csong Jul 27 '15 at 15:14
  • $\begingroup$ I think i have it, if it was Turing Recognizable, then it would be possible to determine when HALT should reject and therefore HALT would be decidable. Since it is not-decidable, then A must be not Turing Recognizable. $\endgroup$ – csong Jul 27 '15 at 15:17
  • $\begingroup$ "problem do is" ​ -> ​ "problem is" ​ ​ ​ ​ $\endgroup$ – user12859 Jul 28 '15 at 9:11

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.