4
$\begingroup$

In a Turing machine I read that it can go only right or to left. But in my book [elements of theory of computation, Book by Christos Papadimitriou and Harry R. Lewis ] it says that Turing machine operates in two discrete steps 1) put the control unit in new state. 2)Either: replace the symbol already there by the symbol currently scanned. Or Move read/write head one tape square left or right

In many online tutorials they say you must move read/write head right/left but you may not change state

Can someone please clear the doubt

$\endgroup$
4
  • 5
    $\begingroup$ There are many definitions around, most of them equivalent. Try proving that you can simulate one with the other! See here for an example of such a proof, if you haven't seen one. You'll either find there's no computational difference -- there may be an efficiency one! -- or you will find out where it lies. $\endgroup$
    – Raphael
    Commented Mar 3, 2020 at 7:03
  • 2
    $\begingroup$ @Raphael Make into a full-fledged answer? $\endgroup$ Commented Mar 3, 2020 at 7:42
  • 1
    $\begingroup$ @YuvalFilmus I think I posted a comment, not an answer. If it is already enough, the question is probably a duplicate of the linked post. $\endgroup$
    – Raphael
    Commented Mar 3, 2020 at 8:43
  • $\begingroup$ Sandeep, your question seems to say that in some tutorials the machine may not change its state. I don't think this is what you meant to write. (Or maybe you misread the tutorials? Perhaps some of them are not written clearly.) It must be possible to change the state in response to reading the tape. Otherwise the state will never change, and machine cannot do different things depending on what is on the tape. $\endgroup$
    – Mars
    Commented Mar 4, 2020 at 4:56

1 Answer 1

4
$\begingroup$

There are a lot of slightly different definitions of Turing machines out there! They usually differ in small but subtle ways. For example, some authors say that a Turing machine's head moves left or right, and writes the symbol; some authors say that it can also stay still. You have seen that Papadimitriou and Lewis allow either replacing the character on the tape, or moving left or right, which is slightly different than both replacing the character on the tape and moving left or right.

That sounds like bad news, but the good news is that you can prove that all of these different definitions are equivalent. Your textbook will have some exercises related to that. For example, we can prove:

  • That Turing Machines that can move left, right, or stay still are equivalent to ones that just move left or right.

    Proof Idea: The Turing Machine that can only move left or right can "mimic" staying still by first moving one step to the right, then moving one step to the left. It takes $2$ steps instead of $1$, but it does the same thing.

  • That Turing Machines that move the head OR write a symbol are equivalent to those that move the head AND write a symbol at each step.

    Proof Idea: the one that moves-or-writes can simulate the behavior of the one that moves-and-writes by first writing, then moving. So it takes $2$ steps instead of $1$, but it does the same thing. On the other hand, the one that moves-and-writes can simulate the behavior of the moves-or-writes one as follows: in order to move without writing, it should write the same symbol that is already on the tape (so that the write has no effect). And in order to write without moving, it should move left and then right, so that there is no net effect.

$\endgroup$

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.