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} \]
The transition function \(\delta: Q \times \Gamma \to (Q \times \Gamma \times \{L,R\})\) maps one state and one letter from \(\Gamma\) to:
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”.
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.