# Equivalence between a TM and a changing TM

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

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.

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'$$.

• Thank you for the help Steven. Before I try the hard part(Simulating a TM with a changing TM) I would like to talk about the "easy" part(A TM can simulate a changing TM). My explanation for this is: Let A be a changing TM , then a TM which is able to simulate A is simply a TM with the restriction of the transition function ,$δ(q,a)=(q^∗,a^∗,c),a≠a^∗$. It seems wrong for me, because its actually the same definition of a changing TM. That is confusing me. Jun 13 '20 at 14:10
• A changing TM A is also a TM, therefore a "TM that simulates A" is just A itself. In other words a changing TM is a TM in which you never perform some kinds of transitions. Jun 13 '20 at 14:13
• Oh, you obviously perform transitions. It is just some kinds of them that are not allowed in a changing TM. To be more precisely, all (and only) the transitions of the form $(q, a) \to (q', a, m)$ are not allowed. I.e., you cannot write the same tape symbol you are reading. Jun 13 '20 at 15:16
• $\gamma_1$ and $\gamma_2$ are just new tape symbols I am using. I could have named them in any other way (I just picked the letter $\gamma$ because they are in the set $\Gamma$). The idea behind this reduction is the one at the end of the first part: if each time we want to write some symbol $b$ on a tape cell we first write $\gamma$ and then $b$ we are always sure that we are obeying the rules of a changing TM (i.e., we never overwrite a symbol with itself). Jun 13 '20 at 15:19
• That is correct. You can save the original symbol on a second tape, as long as the definition of a changing TM allows you to use multiple tapes. It is known that TMs with multiple tapes and TMs with a single tape are equivalent (as far as computability is concerned) so you can freely add tapes to regular TMs. I did not want to prove such a thing for changing TMs (even though it is clearly true) so I did not use extra tapes. Instead I used the machine's states to store the original symbol. Jun 13 '20 at 15:44