I would like to run the following string $w=011101$ on the following NTM and figure out the respective computation branches and whether it accepts or rejects that string.

$\text{Start: }(q_0) 011101 $



$a) 0(q_{rej}) 11101 \:\:\: b) 0(q_{acc}) 11101$

My questions are:

  • Does the T.M continues on $b) 0(q_acc) 11101$ and reads a $1$, thus going to $q_2$ or it halts whenever it hits an accepting or rejecting state?
  • Does the T.M accept the string above?


  • $\begingroup$ It does both, or it does whichever one eventually leads to an accepting state, depending on your interpretation. Since q_reject never leads to an accepting state we can ignore that branch unless it's the only branch left. $\endgroup$
    – user253751
    Aug 31 at 9:40

The final states of a Turing machine (deterministic or not) have immediate effect and terminate the current computation. In your example, you have two final states $q_{acc}$ and $q_{rej}$ which will terminate any computation that reaches one of those state.

Now since there exists a computation that reaches the state $q_{acc}$, your non-deterministic Turing machine will terminate and accept the input. Therefore, your input $w = 011101$ will be accepted.


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.