14
$\begingroup$

Does accepting mean that the TM will read and recognize a char from the cell it's currently reading from? And is it the case that a TM halts iff the input is decidable?

$\endgroup$
2
  • $\begingroup$ Halting is synonymous with terminating (in an accepting/rejecting state). Accepting a language (deciding membership in a language) means halting in an accepting state for all inputs that belong in the language. $\endgroup$
    – mrk
    Sep 15, 2012 at 2:32
  • $\begingroup$ This is a matter of basic definitions. What has been confusing you? $\endgroup$
    – Raphael
    Sep 15, 2012 at 13:08

1 Answer 1

11
$\begingroup$

Accepting and rejecting the state a Turing machine may eventually enter, is based on the string read from the tape, not just the symbol from one cell. Of course, the decision about entering an accepting or rejecting tape is ultimately made on the basis of one symbol.

A Turing machine can either eventually enter an accepting state, enter a rejecting state, or loop forever. If it enters either an accepting or rejecting state, then it halts.

A Turing machine is said to be total if it halts on all inputs.

The language accepted by a Turing machine is the set of all words that that, when provided as input to the Turing machine, cause the Turing machine to enter an accepting state.

A language is said to be decidable if and only if there exists a total Turing machine that will accept the language.

$\endgroup$
1
  • 1
    $\begingroup$ Actually, we should be talking about Turing machine programs. The Turing machine itself is a model. It's an abuse of the expression. $\endgroup$
    – mrk
    Sep 15, 2012 at 2:43

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.