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 $$⟨Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_1,q_{acc},q_{rej}⟩$$ where $$\begin{array}{rl}Q& :\text{finite set of states}\\ \mathrm{\Sigma }& :\text{input alphabet }\mathrm{\Sigma }\subseteq \mathrm{\Gamma }\\ \mathrm{\Gamma }& :\text{the tape alphabet, including the blank symbol }\bigsqcup \\ \delta & :\text{transition function in the form }Q\times \mathrm{\Gamma }\to (Q\times \mathrm{\Gamma }\times \{L,R\})\\ q_1,q_{acc},q_{rej}& :\text{start, accept and reject states, where }{q}_{\cdots }\in Q\end{array}$$

Transition function

The transition function $\delta :Q\times \mathrm{\Gamma }\to (Q\times \mathrm{\Gamma }\times \{L,R\})$ maps one state and one letter from $\mathrm{\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}\to \text{write},\text{direction}$. For example $a\to 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 {\mathrm{\Sigma }}^{\ast }|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.