Reducing States in Modified Turing Machines

[mathmari]

Hey!

I am looking at the following:

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

View attachment 9297

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. Could you give me a hint how we could do that? I don't really have an idea. (Wondering)

 

[I like Serena]

Hey mathmari! (Smile)

Normally a Turing Machine is described with tuples of the form (p, s, q, t, d).
It means that if the machine is in state p and reads symbol s, that it will move to state q, write symbol t, and shift the tape in the direction d (left or right).
What do the symbols in your table mean? In particular $\sqcup$ and $\mid$? (Wondering)

 

[mathmari]

Normally a Turing Machine is described with tuples of the form (p, s, q, t, d).
It means that if the machine is in state p and reads symbol s, that it will move to state q, write symbol t, and shift the tape in the direction d (left or right).
What do the symbols in your table mean? In particular $\sqcup$ and $\mid$? (Wondering)

$\sqcup$ is the space.
$s_i$ are the states, where $s_0$ is the initial state.

I suppose that $\mid$ is the symbol that we can write on the TM. So from the first line of the table we have that the machine is in state $s_0$ and reads the blank symbol $\sqcup$, that it will move to state $s_1$, write symbol $\mid$, and shift the tape to the left.

Respectively we continue at the following lines of the table.

Is that correct? (Wondering) Why is this a modified TM? Can a modified TM write on the TM and move the head with one step but at the ordinary one these are two steps?

 

[mathmari]

At a proposed solution there is the following ordinary TM:

View attachment 9298

 

[I like Serena]

There are different definitions for Turing Machines.
It looks as if in the context of your problem a Modified Turing Machine means that we have 5-tuples that move the state, read a symbol, write a symbol, and move the tape.
And an Ordinary Turing Machine means that we have 4-tuples that move the state, read a symbol, and either write a symbol, or move the tape. (Thinking)

So the problem must be asking for a Turing Machine with such 4-tuples, and also for an equivalent one with at most 8 states. (Thinking)

 

[mathmari]

There are different definitions for Turing Machines.
It looks as if in the context of your problem a Modified Turing Machine means that we have 5-tuples that move the state, read a symbol, write a symbol, and move the tape.
And an Ordinary Turing Machine means that we have 4-tuples that move the state, read a symbol, and either write a symbol, or move the tape. (Thinking)

So the problem must be asking for a Turing Machine with such 4-tuples, and also for an equivalent one with at most 8 states. (Thinking)

Ok! But how do we get the TM with 4-tuples of #4? The states with the apostroph are the intermediate helping states, or not? But which is the idea to find these ones? (Wondering)

 

[I like Serena]

Ok! But how do we get the TM with 4-tuples of #4? The states with the apostroph are the intermediate helping states, or not? But which is the idea to find these ones?

Suppose we have the tuple $(s_0,\sqcup,s_1,|,r)$.
That is, if in state $s_0$ we read a space, we go to state $s_1$, write a $|$, and move the tape right.
We can also do that in 2 steps can't we?
If in state $s_0$ we read a space, we can first go to new state $s_1'$, and write a $|$.
And in state $s_1'$ we can then go to state $s_1$ if we read a $|$, and move the tape right. (Thinking)

 

[mathmari]

Suppose we have the tuple $(s_0,\sqcup,s_1,|,r)$.
That is, if in state $s_0$ we read a space, we go to state $s_1$, write a $|$, and move the tape right.
We can also do that in 2 steps can't we?
If in state $s_0$ we read a space, we can first go to new state $s_1'$, and write a $|$.
And in state $s_1'$ we can then go to state $s_1$ if we read a $|$, and move the tape right. (Thinking)

Ah I see!

Do we apply this idea at each line of the table of #1? So for each line we get two new tuples? (Wondering)

 

[mathmari]

If we do that in that way we get $2\cdot 9=18$ new tuples. How do we get then an equivalent one with at most eight states?

 

[I like Serena]

If we do that in that way we get $2\cdot 9=18$ new tuples. How do we get then an equivalent one with at most eight states?

I think so yes. I did not really check if everything will work out yet.
To find an equivalent one with at most 8 states, we need to simplify what it does somehow.
We could start with checking what the machine is actually doing, and see if we can make a simple 4-tuple machine for it.
What kind of words would it accept? And what would be its output? (Thinking)

 

[mathmari]

So if we write each line of the given table as two lines we get them the following:

View attachment 9301
View attachment 9302

Is that correct? If yes, could you give me a hint how we get an equivalent tm with at most 8 states? (Wondering)

 

[mathmari]

Has the ordinary TM have to be deterministic? Because the given is not because of $s_4$ since we know only what we do if we read the symbol $\mid$ but not what we do when we read the blank. Or is that wrong? (Wondering)

 

[I like Serena]

Has the ordinary TM have to be deterministic? Because the given is not because of $s_4$ since we know only what we do if we read the symbol $\mid$ but not what we do when we read the blank. Or is that wrong?

Wiki says:

In some models, if there is no entry in the table for the current combination of symbol and state, then the machine will halt; other models require all entries to be filled. ​

So I think the given Modified Turing Machine is intended to halt if it reads a blank in state $s_4$.
For the 4-tuple Ordinary Turing Machine it depends on which definition we're using.
We can either define a set of final states, or leave reachable state transition(s) undefined, or both. (Thinking)

 

[mathmari]

Let's consider the first line of the given table: $(s_0,\sqcup,s_1,|,\ell)$

This can be done in two steps as follows:
$(s_0,\sqcup,s_1',|)$
$(s_1',\mid,s_1,\ell)$

So that the resulting TM is deterministic, what has to be done? Do we make it as $(s_1',\sqcup,s_1',\sqcup)$ which doesn't change anything? (Wondering)

 

[I like Serena]

Let's consider the first line of the given table: $(s_0,\sqcup,s_1,|,\ell)$

This can be done in two steps as follows:
$(s_0,\sqcup,s_1',|)$
$(s_1',\mid,s_1,\ell)$

So that the resulting TM is deterministic, what has to be done? Do we make it as $(s_1',\sqcup,s_1',\sqcup)$ which doesn't change anything?

It is already deterministic isn't it?
We can only reach state $s_1'$ after writing a | without moving the tape.
So if we read in state $s_1'$ we can only read a |.
It is not possible to read a blank, so we do not need a state transition for it either. (Thinking)

 

[mathmari]

It is already deterministic isn't it?
We can only reach state $s_1'$ after writing a | without moving the tape.
So if we read in state $s_1'$ we can only read a |.
It is not possible to read a blank, so we do not need a state transition for it either. (Thinking)

I thought so because I saw the following solution (I don't know for sure if that is correct):

View attachment 9306

 

[mathmari]

It is already deterministic isn't it?
We can only reach state $s_1'$ after writing a | without moving the tape.
So if we read in state $s_1'$ we can only read a |.
It is not possible to read a blank, so we do not need a state transition for it either. (Thinking)

But isn't a deterministic TM the one that at each step we have to know where to go no matter what is read? So do we not have to have also a transition for reading a blank? (Wondering)

 

[I like Serena]

But isn't a deterministic TM the one that at each step we have to know where to go no matter what is read? So do we not have to have also a transition for reading a blank? (Wondering)

A deterministic machine is one that behaves deterministically no matter what the input is.
For a Turing machine that is the case if, as wiki puts it:

... the deterministic Turing machine (DTM) for which the action table has at most one entry for each combination of symbol and state.​

(Nerd)

 

[mathmari]

A deterministic machine is one that behaves deterministically no matter what the input is.
For a Turing machine that is the case if, as wiki puts it:

... the deterministic Turing machine (DTM) for which the action table has at most one entry for each combination of symbol and state.​

(Nerd)

Ok! But why do we have at #16 at the (proposed) solution at each step the third line? (Wondering)

 

[I like Serena]

Ok! But why do we have at #16 at the (proposed) solution at each step the third line?

Perhaps the context of the problem defines its Ordinary Turing Machine such that every state - that is not a final state - must have a state transition for all inputs... (Thinking)
After all, we already now that what the problem considers an 'ordinary Turing Machine' is not the definition that wiki gives.

Or perhaps those steps are indeed redundant... (Thinking)

 

[mathmari]

Perhaps the context of the problem defines its Ordinary Turing Machine such that every state - that is not a final state - must have a state transition for all inputs... (Thinking)
After all, we already now that what the problem considers an 'ordinary Turing Machine' is not the definition that wiki gives.

Or perhaps those steps are indeed redundant... (Thinking)

We have the following definition for the transformation:

View attachment 9311

Do we have those steps maybe because of the last part of that definition? (Wondering)

 

[I like Serena]

We have the following definition for the transformation:

Do we have those steps maybe because of the last part of that definition? (Wondering)

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

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

 

[mathmari]

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

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

Is the third line at each step of the proposed solution at #16 justified by the above? (Wondering)

 

[I like Serena]

Is the third line at each step of the proposed solution at #16 justified by the above?

No. It is not.
The above specifies the single transition I suggested and leaves out that third line at each step. (Nerd)

 

[mathmari]

No. It is not.
The above specifies the single transition I suggested and leaves out that third line at each step. (Nerd)

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? (Wondering)

 

[mathmari]

If that is correct, how could we find an equivalent TM with at most $8$ states? For that do we maybe ignore states in the form $(s_0,\mid,s_0',|)$ wheere we read the same as we write? (Wondering)