# Definition:Turing Machine

## Definition

A **Turing machine** is an idealization of a computing machine.

The idea goes as follows.

A **Turing machine** 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.

## 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

- 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next): Entry:**Turing machine** - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next): Entry:**Turing machine**