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.

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?

  • $\begingroup$ 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? $\endgroup$ – DDaren Feb 14 '15 at 23:10
  • $\begingroup$ 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? $\endgroup$ – Mr Tsjolder Feb 15 '15 at 8:50

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.