Turing Machines are the simplest formally defined model which is capable of computing anything that modern computers can compute. This makes them useful for theoretical study. However, devising a Turing Machine that solves a given problem of interest is not always easy. Therefore, there exist several common variants of Turing Machines which have been proven to be equivalent in computational power to a Turing Machine, but provide much more flexibility by increasing the types of steps that can be added to an Turing Machine algorithm. Proofs that a computational model is equivalent in power to a Turing Machine generally involve showing how to construct a Turing Machine given any possible instance of the model. Sometimes devising an algorithm to solve a problem using one of these is far easier, and since we know that they can be converted to a Turing Machine, we don't need to do all that extra work.

A list of common Turing Machine variants, otherwise known as Turing Equivalent machines:

  • Non Deterministic Turing Machine - A Turing Machine which may follow more than one transition per configuration.
  • Multitape Turing Machine - A Turing Machine containing a finite number of tapes greater than 1.
  • Universal Turing Machine - A Turing Machine that is able to store any other Turing Machine on its tape and emulates its function. This is also related to the Recursion Theorem and is one of the more broadly useful (and important) constructs in Computational Theory.
  • Enumerator - A Turing Machine which has a printer attached and prints out lists of strings.

These are useful models in the Theory of Computation, but really any programming language which describes only algorithms (which is all of them, currently) could be considered a Turing Machine variant. Arbitrary languages tend to be far less useful for Theory than the aforementioned machines, so I don't list them.

Less Powerful Computational Models

Turing Machines can also describe less powerful models of computation which can solve subsets of the problems which Turing Machines can solve. These other models can be more practical in terms of hardware costs and implementation, and form the basis for the abundant simple electronic devices that far outnumber computers. Studying what these types of machines can solve is also important, because we can we can know more about their function in general than we can about Turing Machines.

See also: models of computation for a comparison (forthcoming).

Log in or registerto write something here or to contact authors.