# Construct a Turing Machine M' such that if M accepts a then M' accepts a and if M doesnot then M' does not halt

Give a TM $M$. Construct a Turing Machine $M'$ such that

1)if $M$ accepts $a$ then $M'$ accepts $a$ and

2)if $M$ does not accept then $M'$ does not halt.

I am thinking about a 2-tape TM, with tape1 running $M$ and create a loop on tape2 when tape1 does not accept $a$. I have got a few questions:

1. When a TM does not accept an input, does it mean it halts in a non-acceptance state or it does not halt?

2. How can I know if it does not halt? It might run forever.

First of all the answer you have in mind seems rather vague and looks a bit like a detour to me. The second tape isn't necessary to program a loop on a TM.

In your example, you can indeed let $M'$ run TM $M$ first. You now know that $M$ will either run forever (this is okay for $M'$ because $M$ won't accept) or halt. Now $M$ could halt in an accepting state (let $M'$ accept and your TM acts as you want to) or in a rejecting state. If it gets in the rejecting state, you need your machine to get into an infinite loop, but that shouldn't be the problem, should it?
• Thank you. How to show a language such that $a$ codes a TM which does (or not) halt on input $a$ is recursive from the two TMs above? – DDaren Feb 14 '15 at 23:10
• I'm not completely sure whether I get the question, but you could try to assume $M$ decides this language and see what happens with $M'$ then. PS: could you accept this answer if it helped you? – Mr Tsjolder Feb 15 '15 at 8:50