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

Question

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.

Answer 1

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.

To answer your questions:

1. A TM accepts all the strings that make it end in a accept-state, so if the TM ends in a reject-state or gets in an infinite loop for a string, the string isn't accepted. More formally, you could define something like

   TM accepts string iff there exists a sequence of states so that the first state is the starting state, the last state is an accepting state and for every state in the sequence, the next state should be reachable using the transition function.

2. You can only know by reasoning what your machine does on a certain input. For a TM it is allowed to run forever. You should only be careful with infinite loops for strings that you want your TM to accept.

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?