Return to Answer

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 to remove this assumption, but 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 wish to write $a$ on the current tape cell, then transition to state $q$, and move in the direction specified by $m$.

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, and transition to the corresponding state 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 $q'$.

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

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 to remove this assumption, but 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 wish to write $a$ on the current tape cell, then transition to state $q$, and move in the direction specified by $m$.

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, and transition to the corresponding state 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)$
• $( (q', b, m, x), \gamma_1) \to ( (q', b, m, x), \gamma_2, R)$
• $ ( (q', b, m, x), \gamma_2) \to ( (q', b, m, \gamma_1), x, L)$
• $( (q', b, m, \gamma_1), \gamma_2) \to (q', b, m)$

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 to remove this assumption, but 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 wish to write $a$ on the current tape cell, then transition to state $q$, and move in the direction specified by $m$.

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, and transition to the corresponding state 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 $q'$.

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 to remove this assumption, but 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 wish to write $a$ on the current tape cell, then transition to state $q$, and move in the direction specified by $m$.

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, and transition to the corresponding state of $T$.

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 to remove this assumption, but 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 wish to write $a$ on the current tape cell, then transition to state $q$, and move in the direction specified by $m$.

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, and transition to the corresponding state 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)$
• $( (q', b, m, x), \gamma_1) \to ( (q', b, m, x), \gamma_2, R)$
• $ ( (q', b, m, x), \gamma_2) \to ( (q', b, m, \gamma_1), x, L)$
• $( (q', b, m, \gamma_1), \gamma_2) \to (q', b, m)$