# Definition:Turing Machine

This page has been identified as a candidate for refactoring of advanced complexity.In particular: There are several internal definitions in here: program, internal state, etc. Each could be extracted and put into its own page.Until this has been finished, please leave
`{{Refactor}}` in the code.
Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Refactor}}` from the code. |

## Definition

A **Turing machine** is an abstract machine which works by manipulating symbols on an imaginary piece of paper by means of a specific set of algorithmic rules.

To simplify things, the piece of paper being worked on is in the form of a series of boxes on a one-dimensional "tape" divided into squares.

Each square can be either blank or can contain a symbol taken from a finite set, e.g. $s_1, s_2, \ldots, s_\alpha$.

The machine examines one square at a time, and carries out an action determined by both:

- $(1): \quad$ the symbol in the square
- $(2): \quad$ the current internal state of the machine.

The **internal state** of the machine is a way of providing a device that can keep track of the symbols in other squares.

There can be only a finite set of these states, say $q_1, q_2, \ldots, q_\beta$.

The actions that the machine can take are as follows:

- $(1): \quad$ Replace the symbol in the square with another symbol
- $(2): \quad$ Move to examine the square in the immediate left of the current square being looked at
- $(3): \quad$ Move to examine the square in the immediate right of the current square being looked at.

After carrying out an action, the machine may change to a different internal state.

The **program** for the machine is a set of instructions which specify:

- $(1): \quad$ what action to take in
*some*possible combinations of the internal state and symbol in the square currently being read - $(2): \quad$ which internal state the machine moves into after carrying out that action.

Thus the instructions have the following form:

- $q_i \quad s_j \quad A \quad q_t$

which is interpreted as:

"If:

- the machine is in internal state $q_i$

- the symbol in the square currently being examined is $s_j$

then:

- Carry out action $A$
- Move into internal state $q_t$.

The actions can be abbreviated to:

- $L$: Move one square to the left
- $R$: Move one square to the right
- $s_k$: Replace the symbol in the square currently being read with symbol $s_k$.

The computation stops when there is no instruction which specifies what should be done in the current combination of internal state and symbol being read.

### Formal Definition

This page needs proofreading.In particular: This might be too detailed or difficult to read, not to mention possible errors.If you believe all issues are dealt with, please remove `{{Proofread}}` from the code.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Proofread}}` from the code. |

A **Turing machine** is a 7-tuple $\paren {Q, \Sigma, \Gamma, \delta, q_0, B, F}$ that satisfies the following:

- $Q$ is a finite set, the
**states**of the machine. - $\Sigma$ is a finite set, the
**input symbols**. - $\Gamma \supsetneq \Sigma$ is a finite superset of the input symbols, called the
**tape symbols**.- For convenience, we also require that $\Gamma$ and $Q$ are disjoint.

- $\delta : Q \times \Gamma \to Q \times \Gamma \times \set {L, R}$ is a partial mapping, the
**transition function**.- $L$ and $R$ are arbitrary constants called
**directions**.

- $L$ and $R$ are arbitrary constants called
- $q_0 \in Q$ is a distinguished state called the
**start state**. - $B \in \Gamma$ is a distinguished tape symbol called the
**blank**symbol. $B$ must not be an element of $\Sigma$. - $F \subset Q$ be a designated subset of the states called
**accepting states**.

An **instantaneous description** of a Turing machine is a finite sequence of elements of $\Gamma \cup Q$, subject to the following conditions:

- There is exactly one element of $Q$ in the sequence.
- The first entry in the sequence is not $B$.
- The last entry in the sequence is not in $Q$.
- If the last entry in the sequence is $B$, then the second-to-last is in $Q$.

By this definition, an instantaneous description can always be written as:

- $X_m X_{m-1} \dotsm X_2 X_1 q Y Z_1 Z_2 \dotsm Z_{n-1} Z_n$

where $m$ or $n$ may be $0$; $X_i$, $Y$, and $Z_j$ are all elements of $\Gamma$; and $q$ is an element of $Q$.

Additionally, $X_m$ and $Z_n$ are not $B$ if they exist; that is, if $m$ and $n$ are not $0$, respectively.

A **move** reduces one instantaneous description into another by applying the transition function.

We write $A \vdash B$ if a machine with instantaneous description $A$ has, after a single move, instantaneous description $B$.

Let $\map \delta {q, Y} = \paren{q', Y', d}$.

Then there are seven cases to consider:

- If $d = L$ and $m > 0$, and either $n > 0$ or $Y' \neq B$ then:

- $X_m \dotsm X_2 X_1 q Y Z_1 \dotsm Z_n \vdash X_m \dotsm X_2 q' X_1 Y' Z_1 \dotsm Z_n$

- If $d = L$ and $m > 0$, but $n = 0$ and $Y' = B$ then:

- $X_m \dotsm X_2 X_1 q Y \vdash X_m \dotsm X_2 q' X_1$

- If $d = L$ but $m = 0$, and either $n > 0$ or $Y' \neq B$ then:

- $q Y Z_1 \dotsm Z_n \vdash q' B Y' Z_1 \dotsm Z_n$

- If $d = R$ and $n > 0$, and either $m > 0$ or $Y' \neq B$ then:

- $X_m \dotsm X_1 q Y Z_1 Z_2 \dotsm Z_n \vdash X_m \dotsm X_1 Y' q' Z_1 Z_2 \dotsm Z_n$

- If $d = R$ and $n > 0$, but $m = 0$ and $Y' = B$ then:

- $q Y Z_1 Z_2 \dotsm Z_n \vdash q' Z_1 Z_2 \dotsm Z_n$

- If $d = R$ but $n = 0$, and either $m > 0$ or $Y' \neq B$ then:

- $X_m \dotsm X_1 q Y \vdash X_m \dotsm X_1 Y' q' B$

- If $m = 0$, $n = 0$, and $Y' = B$ then regardless of $d$:

- $q Y \vdash q' B$

Let $A \vdash^* B$ indicate that there exists a finite sequence $\sequence {A_i}_{0 \leq i \leq n}$ such that:

- $A = A_0 \vdash A_1 \vdash A_2 \vdash \dotso \vdash A_n = B$

The **language** $\map L M$ accepted by the machine $M$ is the set of strings $w \in \Sigma^*$ for which, for some $\alpha, \beta \in \Gamma^*$ and $p \in F$:

- $q_0 w \vdash^* \alpha p \beta$

As a special case, the null string is in the language if and only if the above holds for $w = B$.

A machine $M$ **halts** on an input $w$, using the same special case for the null string as above, if and only if for some $\alpha, \beta \in \Gamma^*$, $X \in \Gamma$, and $q \in Q$:

- $q_0 w \vdash^* \alpha q X \beta$

where $\map \delta {q, X}$ is undefined.

## Also known as

Such a machine is also known as a **deterministic Turing machine** to distinguish it from the nondeterministic version.

## Also see

- Results about
**Turing machines**can be found**here**.

## Source of Name

This entry was named for Alan Mathison Turing.

## Historical Note

The **Turing machine** was devised by Alan Mathison Turing some time around $1936$.

## Sources

- 2006: John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman:
*Introduction to Automata Theory, Languages, and Computation*(3rd ed.) - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**Turing machine** - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next):**Turing machine**