Skip to main content
added 67 characters in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

When you want to move one position to the left, execute the following algorithm:

  • Mark the current position as special.
  • Move to the origin.
  • Translate the tape one cell to the right, while keeping the special marker in place.
  • Move to the origin.
  • Scan until reaching the special marker.
  • If you move to the right, don't forget to erase the special marker.

(This simulates a Turing machine with a single two-sided tape.)

When you want to move one position to the left, execute the following algorithm:

  • Mark the current position as special.
  • Move to the origin.
  • Translate the tape one cell to the right, while keeping the special marker in place.
  • Move to the origin.
  • Scan until reaching the special marker.
  • If you move to the right, don't forget to erase the special marker.

When you want to move one position to the left, execute the following algorithm:

  • Mark the current position as special.
  • Move to the origin.
  • Translate the tape one cell to the right, while keeping the special marker in place.
  • Move to the origin.
  • Scan until reaching the special marker.
  • If you move to the right, don't forget to erase the special marker.

(This simulates a Turing machine with a single two-sided tape.)

Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

When you want to move one position to the left, execute the following algorithm:

  • Mark the current position as special.
  • Move to the origin.
  • Translate the tape one cell to the right, while keeping the special marker in place.
  • Move to the origin.
  • Scan until reaching the special marker.
  • If you move to the right, don't forget to erase the special marker.