Alan Turing (1912-1954) “invented” the Turing machine (TM) as a powerful theoretical model for mathematicians exploring rules-based mathematics. The Non-deterministic Turing machine, or NTM, extends the basic concept by permitting multiple instructions for one state-input combination.
The Deterministic Turing Machine
A Turing machine has a finite number of states, symbols and instructions. A pattern of symbols are presented on an infinitely long “tape”. The TM reads or rewrites one symbol in one cell of the tape, then moves right or left by one cell. A TM is programmed with instructions. A deterministic Turing machine is limited to one instruction for each state to deal with each symbol, plus optional states to “halt and accept” or “halt and reject” the tape’s initial pattern. A TM either halts or continues processing without halting.
What is a Non-Deterministic Turing Machine?
A non-deterministic Turing machine allows multiple instructions for any one state as it reads any one input symbol. Mathematically, the mapping from the state plus symbol is a relation, rather than a function. Conceptually, a non-deterministic TM runs many isolated computations in parallel.
Another useful concept is a decision tree structure. A node with branches is created each time an NTM begins a parallel computation. Each “leaf” of the decision tree represents a halt state reached by one of the parallel computations.
Is the Non-Deterministic Turing Machine More Powerful than a Standard TM?
Deterministic and non-deterministic TMs have the same computational power – neither is more powerful. Obviously, an NTM can simulate a TM by restricting its instructions to match the TM, but a TM can simulate an NTM also. Using the “decision tree” concept, the TM must construct that NTM’s entire decision tree, at least until finding a “leaf” that represents an “accept” state. A breadth-first construction avoids the danger of falling into a non-halting infinite loop.
Although the NTM could be “faster” than its deterministic simulator, both would produce the same results and therefore have the same computational power.