What is a Turing Machine?

An artist's depiction of a Turing machine.

A Turing machine is an abstract concept used to describe a type of machine that, given an indefinite amount of space and time, can be adapted to calculate anything, such as the digits of π or even a whole universe.

A simple Turing machine consists of a tape of a theoretically infinite size consisting of cells, or sections on the tape. Each cell holds on it a symbol, which is written to it by the head, and which modified the current state of the machine.

There are a finite number of symbols that the head can read or write. Any cells to which the head did not write previously is considered to hold the blank symbol, often designated as ${\displaystyle b}$. This means that at any point during the execution of the Turing machine, there is an infinite amount of blank symbols on the tape.

The initial state, designated by ${\displaystyle q_{0}}$, is the state in which the Turing machine is in at the beginning of execution.

What Different Types of Turing Machines are There?

There are many different types of Turing machines that are often used to describe certain kinds of execution. The two that are most often used are deterministic and non-deterministic Turing machines.

What is a Deterministic Turing Machine?

Automata are often used to represent Turing machines. This is a deterministic Turing machine which calculates the two's complement of some binary input.

A deterministic Turing machine is one that uses the concept of determinism to calculate a solution to a problem.

Determinism is the concept of being only in one state at a given time and determining what the next state will be from that state. In simpler terms, determinism would be being in state ${\displaystyle q_{0}}$, and only holding that state until moving onto the next state, ${\displaystyle q_{1}}$. In determinism we would be able to predict without any doubt that the head would move from state ${\displaystyle q_{0}}$ to state ${\displaystyle q_{1}}$. A Turing machine does not have to even halt, or stop execution, in order for it to be considered deterministic.

What is a Non-deterministic Turing Machine?

A non-deterministic Turing machine is one that uses the concept of non-determinism to calculate a solution to a problem.

A non-deterministic Turing Machine differs from a deterministic Turing Machine in the sense that a non-deterministic Turing Machine can have several possible states to which it can transition from any given state, ${\displaystyle q_{i}}$. One way to think of it would be to think that, given the possibility of choosing from several subsequent states, the non-deterministic Turing machine guesses the next iteration that will bring it to a ‘yes’ answer. Put a different way, the non-deterministic Turing machine branches out into holding many states at the same time in a sort of tree fashion until one of the many paths leads it to a ‘yes’ answer. In perspective a non-deterministic Turing machine may, for instance, be in state ${\displaystyle q_{0}}$ and then hold both state ${\displaystyle q_{1_{1}}}$ as one of the branches and state ${\displaystyle q_{1_{2}}}$ as another branch.