Difference between revisions of "Non-deterministic Turing machine"

Latest revision as of 19:14, 25 April 2016

A non-deterministic Turing machine (NTM) is a Turing machine in which different actions may apply for the same combination of state and symbol.

The original Turing machine is deterministic: it requires a single specific action for a given combination of state and symbol.

Deterministic Turing machines

In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers.

In a deterministic Turing machine, the set of rules prescribes at most one action to be performed for any given situation.

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', change it to 'B' and move left."

A 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, right or neither) in which the head should move
• 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.

Non-deterministic Turing machines

A non-deterministic Turing machine (NTM) may have a set of rules that prescribes more than one action for a given situation.

The state and tape symbol no longer uniquely specify these things. Rather, many different actions may apply for the same combination of state and symbol.

Example 1:

A non-deterministic Turing machine may have both:

• "If you are in state 2 and you see an 'A', change it to a 'B' and move left"
• "If you are in state 2 and you see an 'A', change it to a 'C' and move right" in its rule set.

Example 2:

An X on the tape in state 3 might now allow the NTM to either:

• Write a Y, move right, and switch to state 5
• Write an X, move left, and stay in state 3

See also

• Theoretical computer science
• Turing machine

External links

• Non-deterministic Turing machine @ Wikipedia