1
$\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?

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

$\endgroup$
  • $\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 '17 at 8:05
  • $\begingroup$ As long as there is an accepting path the TM accepts. $\endgroup$ – adrianN Sep 14 '17 at 8:25

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.