2 \langle, \rangle edited Feb 5 '16 at 15:53 cody 7,1421717 silver badges4343 bronze badges Given a Turing Machine $$M$$ you can effectively construct $$M'$$ that does the following: Given $$x$$, $$M'$$ overwrites $$x$$ with $$$$$$\langle M\rangle$$ up to length $$|x|$$ or end of $$$$$$\langle M\rangle$$, whichever comes first. Writes blanks on the rest of $$x$$, and puts an end marker on cell $$|x|+1$$. $$M'$$ returns to the beginning of input and simulates $$M$$. If $$M$$ accesses end marker at any point, $$M'$$ enters an infinite loop without moving any further to the right. If $$M$$ accepts, $$M'$$ goes infinitely to the right. Note this $$M'$$ has the following properties: If $$M$$ halts on $$$$$$\langle M\rangle$$ then $$M'$$ will access $$|x| + 10$$th cell for some large enough $$x$$. If $$M$$ does not halt on $$$$$$\langle M\rangle$$ then $$M'$$ will never access $$|x|+10$$th cell. Given a Turing Machine $$M$$ you can effectively construct $$M'$$ that does the following: Given $$x$$, $$M'$$ overwrites $$x$$ with $$$$ up to length $$|x|$$ or end of $$$$, whichever comes first. Writes blanks on the rest of $$x$$, and puts an end marker on cell $$|x|+1$$. $$M'$$ returns to the beginning of input and simulates $$M$$. If $$M$$ accesses end marker at any point, $$M'$$ enters an infinite loop without moving any further to the right. If $$M$$ accepts, $$M'$$ goes infinitely to the right. Note this $$M'$$ has the following properties: If $$M$$ halts on $$$$ then $$M'$$ will access $$|x| + 10$$th cell for some large enough $$x$$. If $$M$$ does not halt on $$$$ then $$M'$$ will never access $$|x|+10$$th cell. Given a Turing Machine $$M$$ you can effectively construct $$M'$$ that does the following: Given $$x$$, $$M'$$ overwrites $$x$$ with $$\langle M\rangle$$ up to length $$|x|$$ or end of $$\langle M\rangle$$, whichever comes first. Writes blanks on the rest of $$x$$, and puts an end marker on cell $$|x|+1$$. $$M'$$ returns to the beginning of input and simulates $$M$$. If $$M$$ accesses end marker at any point, $$M'$$ enters an infinite loop without moving any further to the right. If $$M$$ accepts, $$M'$$ goes infinitely to the right. Note this $$M'$$ has the following properties: If $$M$$ halts on $$\langle M\rangle$$ then $$M'$$ will access $$|x| + 10$$th cell for some large enough $$x$$. If $$M$$ does not halt on $$\langle M\rangle$$ then $$M'$$ will never access $$|x|+10$$th cell. 1 answered Jan 25 '16 at 16:34 Denis Pankratov 1,37355 silver badges1414 bronze badges Given a Turing Machine $$M$$ you can effectively construct $$M'$$ that does the following: Given $$x$$, $$M'$$ overwrites $$x$$ with $$$$ up to length $$|x|$$ or end of $$$$, whichever comes first. Writes blanks on the rest of $$x$$, and puts an end marker on cell $$|x|+1$$. $$M'$$ returns to the beginning of input and simulates $$M$$. If $$M$$ accesses end marker at any point, $$M'$$ enters an infinite loop without moving any further to the right. If $$M$$ accepts, $$M'$$ goes infinitely to the right. Note this $$M'$$ has the following properties: If $$M$$ halts on $$$$ then $$M'$$ will access $$|x| + 10$$th cell for some large enough $$x$$. If $$M$$ does not halt on $$$$ then $$M'$$ will never access $$|x|+10$$th cell.