We have the following definition for the transformation:
Do we have those steps maybe because of the last part of that definition?
We have the following definition for the transformation:
Do we have those steps maybe because of the last part of that definition?
That transformation converts the Modified Turing Machine into and Ordinary Turing Machine.
First off, it shows that we will indeed have states with only 1 transition in the Ordinary Turing Machine.
That is, the state transition from $s_1'$ to $s$ in the 2nd rule is only defined for the symbol $x'$ and not for any other symbol.
The last part with $\delta(s,x)=\varnothing$ shows that if there are no state transitions at all in state $s$ of the Modified Turing Machine, that we transform it into a state that halts the Ordinary Turing Machine. It means that it is a final state.
At the given table of the modified TM of #1 do we not have $\delta (s_4 ,\sqcup )=\emptyset$ ?
So according to the definition do we not get the following ordinary TM ?
$(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*}
Or have I understood that wrong?
Last edited by mathmari; Today at 18:10.