I am currently trying to prove whether the above language is decidable, partially decidable or fully undecidable. I am certain that this language is partially decidable and reducible to the halting problem. However, I am having trouble actually proving it.

Can anyone assist me with constructing the TM that decides this HALT variant?

What I'm thinking is creating a program that takes M and:

  • if M terminates on w and tape is empty, accept
  • if M terminates on w and tape is not empty, reject
  • if M does not terminate on w, reject
  • 1
    $\begingroup$ "if M does not terminate on w, reject" -- and how do you do that? $\endgroup$ – Raphael Nov 8 '17 at 10:04
  • $\begingroup$ Well, it's under assumption that the halting problem is solvable, but of course it's not so it would prove that the problem is partially decidable.. $\endgroup$ – Ponsietta Nov 8 '17 at 10:10
  • $\begingroup$ I don't think your thinking of this the right way around. You may want to check out our reference questions on showing undecidability and reduction techniques. $\endgroup$ – Raphael Nov 8 '17 at 10:29
  • $\begingroup$ You are using a Turing-reduction argument, but Turing-reduction does not guarantee that if a problem is T-reducible to an r.e. one, such problem is r.e. . You need an m-reduction for that. More concretely, m-reduction does not work by "assuming halt is decidable" (T-reduction sort-of does, but does not help here). $\endgroup$ – chi Nov 8 '17 at 10:40
  • $\begingroup$ Understood, so now I am thinking of proving that it's semi-decidable by m-reduction of accept problem to halt (since this problem seems to be in fact a variant of the accept problem rather than halt). Thus, an accept function can be created that accepts if M accepts and its tape is empty, rejects if M accepts but tape is not empty, and loops forever if M never accepts. Does that sound reasonable? $\endgroup$ – Ponsietta Nov 8 '17 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.