0
$\begingroup$

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 $

$0(q_3)11101$

$(q_1)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?

NTM

Improve this question
$\endgroup$
1
  • $\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, 2021 at 9:40

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.