home

Turing machines

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).

Formal expression

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:

1. the next state of the automaton
2. a letter to be written on the current cell of the tape
3. the direction (Left or Right) 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.