A *Turing machine* is a finite automaton with access to memory. It’s a mathematical model of computation that describes an abstract machine.

It is assumed with unbounded memory, provided by an infinite tape of discrete cells with each cell containing a character (including an ‘empty’ or blank character).

A Turing machine consists of
\[
\langle Q, \Sigma, \Gamma, \delta, q_1, q_{acc}, q_{rej} \rangle
\] where
\[
\begin{align}
Q &: \text{finite set of states} \\
\Sigma &: \text{input alphabet } \Sigma \subseteq \Gamma \\
\Gamma &: \text{the tape alphabet, including the blank symbol } \sqcup \\
\delta &: \text{transition function in the form } Q \times \Gamma \to (Q \times \Gamma \times \{L,R\}) \\
q_1, q_{acc}, q_{rej} &: \text{start, accept and reject states, where } q_\cdots \in Q
\end{align}
\]

### Transition function

The transition function \(\delta: Q \times \Gamma \to (Q \times \Gamma \times \{L,R\})\) maps one state and one letter from \(\Gamma\) to:

- the next state of the automaton
- a letter to be written on the current cell of the tape
- the direction (
**L**eft or **R**ight) the tape head is to move

When annotating this on a state diagram, convention is to mark each edge with \(\text{read} \rightarrow \text{write}, \text{direction}\). For example \(a \rightarrow b, R\) expresses “if the letter under the tape head is \(a\), then write \(b\) and advance the right rightward cell”.

## Language

The language of a given Turing machine, \(M\), is expressed as
\[
\mathcal L (M) = \{ w \in \Sigma^* | M \text{ accepts } w \}
\]
If \(w \in \mathcal L (M)\), \(M\) reaches an accept state. Otherwise if \(w \notin \mathcal L (M)\) this implies the input resulted in a reject state, or enters an infinite loop.

A language is *recognisable* is it is accepted by a Turing machine. The machine itself is termed the *recogniser* of \(\mathcal L(M)\).

Turing machines that do not enter infinite loops are called *deciders*. A language is decidable always result in an explicit accept or reject state being reached.