2
$\begingroup$

I.e. - if a TM accepts the word 0011100 on one path, while on another the same word is rejected. Do we say that 0011100 is part of the language, or do we say that it is not a valid TM?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

A non-deterministic Turing machine accepts a word if an accepting computation exists. There can be many non-accepting computation paths. This is what makes recognizing the complement of the language more difficult than just inverting accepting an rejecting states as you would do with a deterministic machine.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I am talking about more than "not accepting" - is it so even if there an explicit reject state for that string? $\endgroup$
    – Joezer
    Sep 14, 2017 at 8:05
  • $\begingroup$ As long as there is an accepting path the TM accepts. $\endgroup$
    – adrianN
    Sep 14, 2017 at 8:25

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.