Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$$


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

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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