Turing machine with "move to origin" instead of "move left"

Question

You have a Turing machine which has its memory tape unbounded on the right side which means that there is a left most cell and the head cannot move left beyond it since the tape is finished. Unfortunately, you also find that on execution of a head move left instruction, rather than moving to the adjacent left cell, the head moves all the way back to the initial left most cell of the tape. Now figure out whether you can still use this TM effectively. The Turing machine with left initialize is similar to an ordinary Turing machine, but the transition function has the form

$$\delta \colon Q × Γ → Q × Γ × \{R, \mathit{INIT}\}.$$

If $\delta(q, a) = (r, b, \mathit{INIT})$, when the machine is in state $q$ reading an $a$, the machines head jumps to the left-hand end of the tape after it writes $b$ on the tape and enters state $r$. Show that you can program this TM such that it simulates a standard TM.

I can't figure out how to simulate this as standard TM. One thought I have is to copy the content of the tape which is afterwards the left move to the starting point of the tape before making a left move. Any further help would be appreciated.

Answer 1

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.)

Answer 2

Interesting faulty TM!

First, given any standard TM, there exists a TM with one-sided tape that simulates it. Basically, we can split a one-sided tape into odd-numbered cells and even numbered cells. Use odd-numbered cells to represent one side of an ordinary tape and use even-numbered cells to represent the other side of an ordinary tape. The current state of the TM always track whether it is on an odd-numbered or even numbered cell.

Now the question is shifted to how to simulate any given TM whose tape is one-sided. Let $S$ be such a machine. The cells of $S$ are $S_0, S_1, S_2$, $\cdots$.

Let us design a faulty TM $F$ to simulate $S$. The cells of $F$ are $F_0, F_1, F_2$, $\cdots$, where $F_0$ is the origin. Even-numbered cell $F_{2i}$ corresponds to $S_i$. Odd-numbered cells will be selected to function as landmarks. Every odd-numbered cell is initially marked blank, $\mathbb{\color{blue}⯁}$.

• If $S$ moves from $S_i$ to $S_{i+1}$, then $F$ should move from $F_{2i}$ to $F_{2i+2}$. This is easy to implement.

• If $S$ moves from $S_i$ to $S_{i-1}$, then $F$ should move from $F_{2i}$ to $F_{2i-2}$. The idea to implement that is to construct an identifiable array of contiguous cells of some fixed length closer and closer to the intended cell.

  1. First $F$ moves to the right and write $\mathbb{\color{blue}{V}}$ on $F_{2i+1}$. Note that $F_{2i-2}$ is three cells to the left of $\mathbb{\color{blue}{V}}$.
  2. Let $F$ move left, i.e, it goes back to the origin, $F_0$.

  3. $\ \ $

     1. Let $F$ read the first seven cells, keeping track of whether $\mathbb{\color{blue}{V}}$ has been read and on which cell.

        If $i\le 3$, then $F$ must have read $\mathbb{\color{blue}{V}}$ on $F_{2i+1}$. Let $F$ go back to $F_0$ and, then, move to the right $2i-2$ times to reach $F_{2i-2}$. Mission is accomplished.

        Otherwise, Let $F$ go back to $F_0$ and move right to write $\mathbb{\color{blue}{U}}$ on $F_1$. Go back to $F_0$.

     2. Now $F$ is on $F_0$. $\mathbb{\color{blue}{U * ⯁ * ⯁ * ⯁}}$ sits somewhere before $\mathbb{\color{blue}{V}}$, where each $\mathbb{\color{blue}{*}}$ stands for a possibly different tape symbol that is neither $\mathbb{\color{blue}U}$ nor $\mathbb{\color{blue}V}$. Except that $\mathbb{\color{blue}{U}}$ and $\mathbb{\color{blue}V}$, all odd-numbered cells are blanks.

        Keep $F$ moving to the right. When it reaches $\mathbb{\color{blue}{U}}$, change it to a blank. Moving two more cells to the right, mark $\mathbb{\color{blue}{U}}$ on the cell. Now we have $\mathbb{\color{blue}{⯁ * U * ⯁ * ⯁}}$ in place of the original stripe.

        Let $F$ move to the cell to the immediate right of the last $\mathbb{\color{blue}⯁}$ above.

     3. If $F$ reads $\mathbb{\color{blue}{V}}$, then we know that $F$ should, for simulation, go to the cell right after $\mathbb{\color{blue}{U}}$. Let $F$ move left, then move right until it reaches $\mathbb{\color{blue}{U}}$. Move right one more time. Mission is accomplished. Note $F$ should also restore $\mathbb{\color{blue}{V}}$ and $\mathbb{\color{blue}{U}}$ to $\mathbb{\color{blue}⯁}$ along the way.

     4. Otherwise, $F$ does not read $\mathbb{\color{blue}{V}}$. That means we have $\mathbb{\color{blue}{U * ⯁ * ⯁ * ⯁}}$ somewhere before $\mathbb{\color{blue}{V}}$ again, but two cells closer. Let $F$ move left. Go back to step 3.2.

The above design concentrates on the ability of $F$ to move like $S$. To simulate $S$, $F$ should also keep track of the current state of $S$, which is easy to implement.

Answer 3

1. you can simulate Standard-TM -> "TM without left option" S.T. a) put a new alphabet at the first place (leftmost) of the tape b) shift all other written into one place right for each init move we go left until we reach out new alphabet

---

2. you can simulate "TM without left option" -> Standard-TM S.T. for every time you needed a left move: a) mark where you are b) using init go back to the beginning and mark there c) we go right until we reach a marked d) we move right one place again if it is already marked that means we reach what we wanted and the previous place was where we need -- > SO : unmark here - > go initial -> move right until reach mark -> here is previous and we are done! e) if it was unmarked -> mark here -> go all the way back to the beginning then move right until the first marked place, unmark there and go to the beginning of the tape.

---

so both have equal power