NTMF: non-deterministic Turing machine Framework
In theoretical computer science, a non-deterministic Turing machine
Framework(NTMF) is a Turing machine whose control mechanism works like a
non-deterministic finite automaton.
Description
An ordinary (deterministic) Turing machine (DTM) has a transition function that,
for a given state and symbol under the tape head, specifies three things: the
symbol to be written to the tape, the direction (left or right) in which the
head should move, and the subsequent state of the finite control. For example,
an X on the tape in state 3 might make the DTM write a Y on the tape, move the
head one position to the right, and switch to state 5.
An NTM differs in that the state and tape symbol no longer uniquely specify
these things - many different actions may apply for the same combination of
state and symbol. For example, an X on the tape in state 3 might now allow the
NTM to write a Y, move right, and switch to state 5 or to write an X, move left,
and stay in state 3.
How does the NTM "know" which of these actions it should take? There are two
ways of looking at it. One is to say that the machine is the "luckiest possible
guesser"; it always picks the transition which eventually leads to an accepting
state, if there is such a transition. The other is to imagine that the machine
"branches" into many copies, each of which follows one of the possible
transitions. Whereas a DTM has a single "computation path" that it follows, a
NTM has a "computation tree". If any branch of the tree halts with an "accept"
condition, we say that the NTM accepts the input.
Definition
More formally, a non-deterministic Turing machine is a 6-tuple , where
Q is a finite set of states
Σ is a finite set of symbols (the tape alphabet)
is the initial state
is the blank symbol ()
is the set of accepting states
is a multivalued function over states and symbols called the transition
function, where L is left shift and R is right shift. In conventional Turing
machines, the transition function is not multi-valued.
Variations
There are a considerable number of variations on this definition. The initial
state may be replaced by a set of initial states, for example. (This is
equivalent because it is trivial to simulate multiple start states by adding a
single start state which nondeterministically chooses which of the multiple
start states to continue with.)
The variation may also include a set of rejecting states, in which case the NTM
is said to reject if all computation paths lead to rejecting states.
Equivalence with DTMs
Intuitively it might seem that NTMs are more powerful than DTMs, since they can
execute many possible computations at once, requiring only that any one of them
succeeds. But any language recognized by a NTM can also be recognized by a DTM:
the DTM can simulate each transition of the NTM, making multiple copies of the
simulated state when multiple transitions are possible, and simulating them all
in parallel, not unlike processes in a multitasking operating system.
It should be apparent that this simulation may require significantly longer
time. How much longer is not known in general - this is, in a nutshell, the
definition of the "Is P = NP?" problem (see Complexity classes P and NP).
Bounded Non-determinism
An NTM has the property of bounded non-determinism, i.e., if an NTM always halts
on a given input tape T then it halts in a bounded number of steps, and
therefore can only have a bounded number of possible configurations.
Comparison with Quantum Computers
It is a common misconception that quantum computers are NTMs. It is believed
that the power of polynomial time quantum computers is incomparable to that of
polynomial time NTMs. That is, for each of the two models, there is a problem
that the one can solve but the other most probably cannot. A likely example of
problems solvable by NTMs but not by polynomial time quantum computers are
NP-complete problems.
