# Decidability of {(M,w); M terminates on input w and tape of M is empty after computation}

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
• "if M does not terminate on w, reject" -- and how do you do that? – Raphael Nov 8 '17 at 10:04
• 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.. – Ponsietta Nov 8 '17 at 10:10
• 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. – Raphael Nov 8 '17 at 10:29
• 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). – chi Nov 8 '17 at 10:40
• 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? – Ponsietta Nov 8 '17 at 19:16