Modified - Ordinary Turing Machine

Question

I am looking the following:

The Turing table of the following modified Turing machine is given:

Change this into an ordinary "Turing machine" (i.e., one that either writes or moves the head). Give the appropriate Turing table. Give also the Turing table of an equivalent (unmodified) Turing machine with at most eight states and justify the equivalence.

The following definition of the transformation is given:

$$$$

I have done the following:

$(s_0,\sqcup,s_1,|,\ell)$ gets $(s_0,\sqcup,s_1',|), (s_1',\mid,s_1,\ell)$

$(s_0,\mid,s_0,|,\ell)$ gets $(s_0,\mid,s_0',|), (s_0',\mid,s_0,\ell)$

$(s_1,\sqcup,s_2,|,r)$ gets $(s_1,\sqcup,s_2',|), (s_2',\mid,s_2,r)$

$(s_1,\mid,s_1,|,r)$ gets $(s_1,\mid,s_1'',|), (s_1'',\mid,s_1,r)$

$(s_2,\sqcup,s_0,|,\ell)$ gets $(s_2,\sqcup,s_0'',|), (s_0'',\mid,s_0,\ell)$

$(s_2,\mid,s_3,|,r)$ gets $(s_2,\mid,s_3',|), (s_3',\mid,s_3,r)$

$(s_3,\sqcup,s_0,|,\ell)$ gets $(s_3,\sqcup,s_0''',|), (s_0''',\mid,s_0,\ell)$

$(s_3,\mid,s_4,|,r)$ gets $(s_3,\mid,s_4',|), (s_4',\mid,s_4,r)$

$(s_4,\mid,s_2,\sqcup,r)$ gets $(s_4,\mid,s_2'',\sqcup), (s_2'',\sqcup,s_2,r)$

Now we have that \begin{align*}\delta (s_1', \sqcup)&=\delta (s_0', \sqcup)=\delta (s_2', \sqcup)=\delta (s_1'', \sqcup)=\delta (s_0'', \sqcup)\\ & =\delta (s_3', \sqcup)=\delta (s_0''', \sqcup)=\delta (s_4', \sqcup)=\delta (s_4, \sqcup)\\ & =\delta (s_2'', \mid)=\emptyset \end{align*} or not?

So according to the last line of the definition we have to add for each of these ones an additional transition, which are the following:

\begin{align*}&(s_1', \sqcup, s_1',h), \ (s_0', \sqcup, s_0', h), \ (s_2', \sqcup, s_2', h), \ (s_1'', \sqcup, s_1'', h), \ (s_0'', \sqcup, s_0'', h)\\ & (s_3', \sqcup, s_3', h), \ (s_0''', \sqcup, s_0''', h), \ (s_4', \sqcup, s_4', h), \ (s_4, \sqcup, s_4, h), \ (s_2'', \mid, s_2'', h) \end{align*}

Is everything correct? Or have I understood that wrong?

$$$$

If that is correct, how could we find an equivalent TM with at most $8$ states?

Answer 1

First, allow me to point out that the 'modified' Turing machine formalization is more often referred to as the 'quintuple' formalization: all transitions are quintuples:

1. If you are in state $s$ and
2. read symbol $x$, then
3. go to state $s'$ and
4. write symbol $x'$ and
5. make a move (right, left, or stay)

The 'unmodified' Turing-machine is more often referred to as the 'quadruple' formalization:

1. If you are in state $s$ and
2. read symbol $x$, then
3. go to state $s'$ and
4. either write symbol $x'$ or make a move (right, left, or stay)

Also, in my Answer below, please allow me to use a $0$ for the $\sqcup$ symbol, and a $1$ for the $|$ symbol.

OK, so we have a quintuple definition, which I'll depict below:

Your first task was to transform this to a quadruple formalization following the transformation definition, and you came up with:

Note, this machine does not have explicit halting transitions, as it is not supported by the software I am using here, so they are left implicit. For example, there is no transition for being in state $s_0'$ and reading a $0$ ... but that is understood as the machine halting. Anyway, your transformation was completely correct: good job!

However, this new machine has $14$ states ... so how can you get a machine with just $8$ states?

Well, first note that any quintuple transition of the form $<s_i, x , s_j, x, m>$ does not require the addition of an extra state. You can just make that $<s_i, x , s_j, m>$, because the symbol read does not get changed.

For example, there is no need for an additional state $s_0'$: you can just transform $<s_0,1,s_0,1,l>$ into $<s_0,1,s_0,l>$. Likewise, states $s_1''$, $s_3'$, and $s_4'$ are unnecessary. So, that immediately cuts down the number of states to $10$:

Second, note that you transformed $<s_3,0,s_0,1,l>$ into $<s_3,0,s_0''',1>$ and $<s_0''',0,s_0,l>$. However, there is no need for that additional state $s_0'''$ either: you can just use a simple $<s_3,0,s_0,1>$ transition directly from $s_3$ to $s_0$, because that transition that says that you have to go left when seeing a $1$ will be taken care of by the $<s_0,1,s_0,l>$ transition: once you are in $s_0$, you will indeed move left when seeing a $1$. Likewise, state $s_0''$ is unnecessary. So, now you are down to $8$ states: