# Non-Deterministic Turing Machine Transition Function

Say a Non-Deterministic Turing Machine is in a state $q_1$ and it reads symbol $a$ from its tape. Is it possible to have two different transitions:

$$(q_1,a) \rightarrow (q_{accept}, <space>, L)$$

and

$$(q_1,a) \rightarrow (q_{reject}, <space>, L)$$

-

Bluntly, yes. Though (depending on which precise definition of a TM you're using) the second will never get used, as a nondeterministic machine will always follow an accepting computation path, if it exists.

-

It certainly doesn't stop the machine from being a well-formed nondeterministic Turing machine.

Of course, if $(q_1,a)$ is reachable, then you will end up with a machine that for some inputs is able to accept as well as to reject. Whether that is a problem or not depends on how you're planning to interpret the machine's result.

The most common way to interpret non-determinism (such as when defining NP and like complexity classes) is that we're only concerned with whether it is possible for the nondeterministic machine to accept or not. In this view, there is no relevant difference between rejecting and diverging, and so it doesn't really matter whether the machines moves to $q_{\rm reject}$ or to an explicit infinite loop.

However, there is nothing that prevents you from declaring that in your particular application you only want to consider machines with the property that there is no possible input on which the machine can both accept and reject. The class of such machines is not decidable, but that is not much different from declaring in some other context that we only want to consider always-terminating deterministic machines.

So it really depends on which behavior you expect from your machine.

-