Editing Nondeterministic Turing machine (section)

==Background==
In essence, a Turing machine is imagined to be a simple computer that reads and writes symbols one at a time on an endless tape by strictly following a set of rules. It determines what action it should perform next according to its internal ''state'' and ''what symbol it currently sees''. An example of one of a Turing Machine's rules might thus be: "If you are in state 2 and you see an 'A', then change it to 'B', move left, and switch to state 3."

===Deterministic Turing machine===
In a [[deterministic Turing machine]] (DTM), the set of rules prescribes at most one action to be performed for any given situation.

A deterministic Turing machine 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 (it may be the same as the symbol currently in that position, or not even write at all, resulting in no practical change), 
*the direction (left, right or neither) 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.