1
$\begingroup$

Say I want to make a very simple Turing Machine that accepts only strings that contain one or more a's. Can I simply send have the machine move a HALT state once it reads one a, even if there are many letters after that first a? Or would this be bad practice or unacceptable for a Turing Machine?

$\endgroup$
1
  • $\begingroup$ Depends on the exact definition you are using. $\endgroup$
    – Raphael
    Nov 13 '14 at 7:08
1
$\begingroup$

To the title question - no, to the flipped version of the same question in the body - yes. It is typically fine to halt without processing the entire input (however see Raphael's answer for certain technicalities in this respect).

There's not really such a thing as "good" or "bad" practice with a Turing Machine in the sense that there are "good" and "bad" practices when programming on a "real" computer.

As they are theoretical models for computations, they are at their best when they prove (or assist in proving) what you need to prove in as clear and direct manner as possible. In this light, as long as your machine only performs permissible actions, then everything is fine - so no cheating, but beyond that it's all good.

$\endgroup$
2
  • $\begingroup$ Thanks. I wonder also if it depends on the book (if mentioned at all). For example I have a computer theory book that makes the tape infinite only in one direction, not both. $\endgroup$
    – btalbot
    Nov 13 '14 at 3:27
  • $\begingroup$ @btalbot, the tape can be infinite in one or both directions, they're equivalent in terms of computing power, so even with that, you can use whichever makes sense for what you need. $\endgroup$ Nov 13 '14 at 3:49
1
$\begingroup$

There are definitions of Turing machines in which the output is defined to be the tape content from the head on to the right (until the first empty cell) at termination. Depending on whether you allow your TM to (re)write empty cells, you have to more to the right or erase most of the input, or at least insert a gap after your output.

There are special (sub)models for deciders and acceptors. In these, there is no output on the tape; there are special (non-)accepting states in which the TM halts. In such models, you can terminate whenever you want without having to worry about the tape content.

$\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.