0

So let's say that we have state 1 2 and 3.

In both the non-deterministic and the deterministic turing machine, we only have one-way transitions between the state 1, 2 and 3. For example, if we can go to state 3 from state 2, we can't go to state 2 from state 3, nor can we go directly to either state 1 or 3 from state 2, am I right?

Another example if we can go to state 2 from state 1, and to state 3 from state 2, and to state 1 from state 3, there are no more paths possible, more specifically, we can't go to state 3 from state 1.

john
  • 21

1 Answers1

0

No, there's no such restriction. For instance, there's a Turing machine whose transition function is "if in state 1, move right and switch to state 2; if in state 2, move left and switch to state 1." This machine ignores the input, never writes anything, and loops forever. None of this has any relation to the question of whether the machine is deterministic.

Kevin Carlson
  • 52,457
  • 4
  • 59
  • 113