Equivalence between a TM and a changing TM

Question

Let a changing TM be a TM which is not able to write the same symbol which is being read. Formal: $M^*=(Q,\Sigma,\Gamma,\delta,q_{accept},q_{reject})$,$\delta(q,a)=(q^*,a^*,c),a \neq a^*$ with $q,q^* \in Q, a,a^* \in \Gamma, c \in \{R,L\}$ . Now I need to proof that a changing TM is equivalent to a normal TM.

My guess was to create a multi-tape TM which is able to simulate the changing TM(and therefore a TM is equivalt to a changing TM, since every multi Tape TM has equivalent single tape TM), but I am unnable to finish(write it formal and unformal down).

Answer 1

This is another easy way to prove that a changing TM can simulate a TM. The advantage of this solution over the previous one is that it works without any additional tedious work regardless of whether the "stay" movement is allowed.

Let $T$ be a TM with tape alphabet $\Gamma$. Create a changing TM $T'$ with the same state space and a tape alphabet $\Gamma'$ with $2|\Gamma|$ symbols: for each symbol $a \in \Gamma$ add both $a$ and a new symbol $a'$ to $\Gamma'$.

For each transition $(q,a) \to (q', b, m)$ of $T$ add the following transitions to $T'$ (notice that you might have $a=b$):

• $(q, a) \to (q', b', m)$
• $(q, a') \to (q', b, m)$

In other words you are treating two symbols $a$ and $a'$ as if they were identical. Whenever you read a "regular" symbol (i.e., one from $\Gamma$) you will write a "prime" symbol. Whenever you read a "prime" symbol (i.e., one from $\Gamma' \setminus \Gamma$) you will write a "regular" symbol.

Answer 2

It is clear that a TM can simulate a changing TM, so you only need to show the converse. Let me allow to use the "stay" movement in the changing Turing machine. It is easy (but tedious) to remove this assumption and keeping it makes the following argument more intuitive.

You can do the following: start from a TM $T$ with set of states $Q$ and tape alphabet $\Gamma$. Then, create a changing TM $T'$ with states $Q' = Q \cup (Q \times \Gamma \times \{L,R\})$ and tape alphabet $\Gamma' = \Gamma \cup \{ \gamma \}$.

Intuitively, state $q \in Q$ of $T'$ represents state $q$ of $T$, while state $(q, a, m) \in Q \times \Gamma \times \{L,R\}$ of $T'$ represents the fact that we plan to write $a$ on the current tape cell, then transition to state $q$, and move in the direction specified by $m$ (notice that this a state, not a transition, we are just keeping track of our future plans).

Replace each transition $(q, a) \to (q', b, m)$ of $T$ with the following transitions in $T'$:

• $(q, a) \to ( (q', b, m), \gamma, S)$, and
• $( (q', b, m), \gamma) \to (q',b, m)$

Intuitively, this replaces the writing of a symbol $b$ on the tape with two operations: 1) we write $\gamma$ without moving the head, and 2) we overwrite $\gamma$ with $b$, move the head in the intended direction $m$, and transition to the corresponding state $q'$ of $T$.

---

This is a tedious simulaton of a TM with a changing TM if the "stay movement" is not allowed. Define $\Gamma' = \Gamma \cup \{\gamma_1, \gamma_2\}$ and $Q'= Q \cup (Q \times \Gamma \times \{L,R\} \times \Gamma')$. Replace each transition $(q, a) \to (q', b, m)$ of $T$ with the following transitions in $T'$:

• $(q, a) \to ( (q', b, m, \gamma_1), \gamma_1, R)$,
• $( (q', b, m, \gamma_1), x) \to ( (q', b, m, x), \gamma_2, L)$ $\quad \forall x \in \Gamma$,
• $( (q', b, m, x), \gamma_1) \to ( (q', b, m, x), \gamma_2, R)$ $\quad \forall x \in \Gamma$,
• $ ( (q', b, m, x), \gamma_2) \to ( (q', b, m, \gamma_1), x, L)$ $\quad \forall x \in \Gamma$,
• $( (q', b, m, \gamma_1), \gamma_2) \to (q', b, m)$

What we are doing is the following: 1) We write $\gamma_1$ and move right, 2) we store the current tape symbol $x$, replace it with $\gamma_2$, and move left, 3) we replace the tape symbol $\gamma_1$ with $\gamma_2$ and move right, 4) we write back the stored type symbol $x$ in place of $\gamma_2$ and move left, 5) we finally write $b$, move according to $m$, and transition to state $q'$.