2 \langle, \rangle
source | link

Given a Turing Machine $M$ you can effectively construct $M'$ that does the following:

  • Given $x$, $M'$ overwrites $x$ with $<M>$$\langle M\rangle$ up to length $|x|$ or end of $<M>$$\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 $<M>$$\langle M\rangle$ then $M'$ will access $|x| + 10$th cell for some large enough $x$.
  • If $M$ does not halt on $<M>$$\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 $<M>$ up to length $|x|$ or end of $<M>$, 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 $<M>$ then $M'$ will access $|x| + 10$th cell for some large enough $x$.
  • If $M$ does not halt on $<M>$ 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
source | link

Given a Turing Machine $M$ you can effectively construct $M'$ that does the following:

  • Given $x$, $M'$ overwrites $x$ with $<M>$ up to length $|x|$ or end of $<M>$, 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 $<M>$ then $M'$ will access $|x| + 10$th cell for some large enough $x$.
  • If $M$ does not halt on $<M>$ then $M'$ will never access $|x|+10$th cell.