Turing machine

Definition

A Turing machine is a tuple $M = (Q, \Gamma, \sqcup, \Sigma, \delta, q_0, F)$ with the following parts.

1. $Q$ is a finite nonempty set of states.
2. $\Gamma$ is a finite set of tape symbols, and $\sqcup \in \Gamma$ is the blank symbol.
3. $\Sigma \subseteq \Gamma \setminus \set{\sqcup}$ is the set of input symbols.
4. $q_0 \in Q$ is the initial state, and $F \subseteq Q$ is the set of halting states.
5. $\delta$ is a partial function from $(Q \setminus F) \times \Gamma$ to $Q \times \Gamma \times \set{L, R}$, the transition function.

A configuration consists of a state $q$, a tape $t \colon \Z \to \Gamma$ with only finitely many non-blank cells, and a head position $p \in \Z$. If $\delta(q, t(p)) = (q', s, D)$, the next configuration has state $q'$, the symbol $s$ written at cell $p$, and head position $p - 1$ if $D = L$ and $p + 1$ if $D = R$. The machine halts when no transition applies, in particular when it reaches a state in $F$. On an input word $w \in \Sigma^*$, the computation starts in state $q_0$ with the head at cell $0$. At the start, $w$ is written from cell $0$ onward and all other cells are blank.