Turing machine

The Turing Machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or 'mechanical procedure'. The concept is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. The thesis that states that Turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as the Church-Turing thesis.

Deterministic and non-deterministic Turing machines

If the action table has at most one entry for each combination of symbol and state then the machine is a deterministic Turing machine (DTM). If the action table contains multiple entries for a combination of symbol and state then the machine is a non-deterministic Turing machine (NDTM or NTM).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~