Non-deterministic turing machine

A Turing machine is an idea from computer science that tries to describe how some computers work. Deterministic Turing machines use a function. Given the current state of the Turing machine, it selects another state the Turing machine should have. In other words, from each state there is one other state the machine can have. A non-deterministic Turing machine uses a relation. This means that from some states there are several other states that are possible.

Non-deterministic Turing Machine Media

Comparison of deterministic and nondeterministic computation
The suspected shape of the range of problems solvable by quantum computers in polynomial time (BQP). Note that the figure suggests \mathsf P \neq \mathsf{NP} and \mathsf{NP} \neq \mathsf{PSPACE}. If this is not true then the figure should look different.

This short article about technology can be made longer. You can help Wikipedia by adding to it.