Turing machine

Not to be confused with Turing-machine.

A Turing machine is an imaginary machine devised by Alan Turing which performs computations. It consists of a finite-state automaton (often called its "control mechanism" or program) hooked up to an unbounded tape which can be moved to the left and right, from which symbols can be read, and onto which symbols can be written.

A universal Turing machine is a Turing machine which can be given a description of any arbitrary Turing machine encoded in some form, initialized on its tape, and the finite state machine operates on the description in such a way that the described machine is simulated. Universal machines are named for the fact that they can compute any computable sequence.

Turing machines are computationally significant because, while many systems of computation have been shown to be able to solve only a subset of computation problems that a given Turing machine can solve, no system of computation definable as a set of algorithms has ever been shown to be able to solve a computation problem that a Turing machine cannot.

In addition, no well-defined algorithm has yet been devised that a universal Turing machine is demonstrably incapable of executing. This has led to the Church-Turing thesis, which states (roughly) that Turing machines are mechanical embodiments of (what we think of intuitively as) effectively computable algorithms. That is to say, a Turing machine can make any sort of calculation that it is possible to precisely define an algorithm for.

Since the invention of Turing machines in Alan Turing's paper, many other systems have been shown to be equivalent to them. (In fact, several of these systems, such as the lambda calculus, combinatory logic, and Post canonical systems, predate the Turing machine.) In this way, Turing machines define a computational class of equivalent systems; these systems are termed Turing-complete.

For all these reasons, it is often an interesting and/or valuable task to show that an esoteric programming language is (or is not) equivalent to a Turing machine.

Formally, Turing machines are often described in a tuple format, $(\Sigma ,\sigma _{0},Q,q_{1},q_{h},f)$ , consisting of:

A set of symbols $\Sigma$
A blank symbol $\sigma _{0}$
A set of states $Q$
A starting state $q_{1}$
A halting state $q_{h}$
A transition function $f:Q\times \Sigma \rightarrow \Sigma \times D\times Q$ $f:Q\times \Sigma \rightarrow \Sigma \times D\times Q$
- Where $D$ is generally either $\lbrace left,\ center,\ right\rbrace$ or $\lbrace left,\ right\rbrace$
- Undefined for $q_{h}$
- Taking in the current state and currently observed symbol, then producing a new symbol to overwrite the observed, a direction to move in, and the next state to transition to

A Turing machine described this way can be thought of a partial function $\Phi :\Sigma ^{\ast }\rightharpoonup \Sigma ^{\ast }$ taking in a preset tape of symbols of some finite length, and producing (through the mutative operation of the machine) a new finite string of symbols on the tape. Since the set $\Sigma ^{\ast }$ is countably infinite, the partial function of a Turing machine can also be written as $f:\mathbb {N} \rightharpoonup \mathbb {N}$ for some encoding scheme between the naturals and symbol strings. The function is partial since the machine may loop indefinitely instead of producing an answer. The notation for a Turing machine $M$ which halts on an input tape $x$ is $M(x)\downarrow$ , and one which does not halt on that input is $M(x)\uparrow$ .