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$
0

1 Answer 1

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$
3
  • $\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$
    – PlsWork
    Jul 20, 2017 at 7:00
  • $\begingroup$ This doesn't work if $q_1$ is an accepting state, your construction skips it. $\endgroup$
    – PlsWork
    Jul 20, 2017 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, 2017 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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