1
$\begingroup$

If we have a Turing machine in a model with a tape that is infinite only to the right and assume at some point the head tries to move left from the leftmost position.

How should we define the behavior in such a case? Is a machine doing so for some input not a valid Turing machine? And if so, how can we make sure when we define a Turing machine that this situation can't occur for any input?

I've read some sources about Turing machines though couldn't find the answer to this specific case, and I see no reason why this case won't happen for an arbitrary Turing machine and some input.

$\endgroup$
3
$\begingroup$

There is no single accepted model of Turing machines. Different choices would lead to very similar models, which simulate each other with very small overhead. That's why we usually don't care so much about the exact model.

Here are some possibilities:

  • If the Turing machine attempts to move to the left of the origin, then the head stays put. The Turing machine might or might not be notified.
  • The Turing machine has a mechanism to detect that it has reached the origin, and cannot move to the left of it (the specs don't allow it).
  • Same, but not the machine can move to the left, and crashes if it attempts to do so (you decide how to interpret a crash – acceptance, rejection, infinite loop).
  • If a Turing machine attempts to move to the left of the origin, then instead it moves right. This makes sense if the Turing machine is guaranteed to always move at every step.

You can probably think of several other alternatives.

$\endgroup$

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.