3
$\begingroup$

I stumbled upon these two defintions of a turing machine:

http://www.cs.um.edu.mt/gordon.pace/Teaching/Complexity/CoursePage/Notes/chapter5.pdf

http://scholar.harvard.edu/files/harrylewis/files/s6_sols.pdf

The difference which bothers me is that the second one allows only left and right movements whereas the first allows left, right and not moving the head at all.

First definition: $\delta_1: Q_1 \times \Gamma_1 \mapsto Q_1 \times \Gamma_1 \times \{L,R,S\}$

Second definition: $\delta_2: Q_2 \times \Gamma_2 \mapsto Q_2 \times \Gamma_2 \times \{L,R\}$

Are they equivalent? If they are equivalent it should be possible to transform a TM that can do $\{L,R,S\}$ into a TM which always has to move left or right (does only $\{L,R\}$)?

How is this possible?

$\endgroup$
1
$\begingroup$

Yes they are equivalent and it is always possible. Informally: you can exchange any $S$ move state with pair of states that goes $L$ then $R$ (or in the other direction).

Formally:
Prove that standard Turing Machine is equivalent to class of Turing Machines with $S$ (no move).
Let $M$ denote standard TM, there exists a TM $M'$ with no move option such that $L(M) = L(M')$. This way is trivial, simply do not use $S$ move in the extended version.
In the other direction:
Given TM $M'$ with no move option, construct equivalent TM $M$ such that $L(M') = L(M)$.
Construct new transition function $\delta'$ for $M$ such that for each state with move $\in \{L, R\}$ in $\delta$ there is equivalent state in $\delta'$.
For each $S$ move in $\delta$ put two states in $\delta'$.
So for $\delta(q_x, a, b, S, q_y)$ put two states to $\delta'$, $\delta(q_x, a, b, L, q_n)$ and $\delta(q_n, *, *, R, q_y)$. The $q_n$ matches the acceptance with $q_x$. If the $S$ move was accepting state, make the second state accepting. This gives the equivalence in the accepting states and the head (heads) position.
$L(M') = L(M)$, so these classes are equivalent.

$\endgroup$
  • $\begingroup$ Sounds reasonable. Do you have a suggestion about how to write this idea down in terms of the $\delta$ functions of both definitions? $\endgroup$ – Anna Vopureta Jul 20 '17 at 7:00
  • $\begingroup$ This doesn't work if $q_1$ is an accepting state, your construction skips it. $\endgroup$ – Anna Vopureta Jul 20 '17 at 12:08
  • $\begingroup$ @AnnaVopureta I have changed whole post, as I understood you want formal method of equivalence not manual method. I hope it is ok now. $\endgroup$ – Evil Jul 21 '17 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.