Computation branches on NTM

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?

• 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. Aug 31 at 9:40

1 Answer

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.