Turing Machines briefly defined

A Turing machine is composed of an infinite tape bounded on the left, a read-write tape head, and a finite control.

A Turing Machine (TM) is described by the tuple

$$M = \left ( Q, \Sigma, \Gamma, \delta, q_{0}, B, F \right ),$$ (1)

where

Q

is the finite set of states,

$\Gamma$

is the the finite set of allowable tape symbols,

B

is the blank symbol ($B \in \Gamma$).

$\Sigma$

is the set of input symbols, $\Sigma \subset \Gamma, B \notin \Sigma$.

$\delta$

is the next move function, $\delta(Q \times \Gamma) \rightarrow Q \times \Gamma \times \{L,R\}$.

q₀

is the start state ($q_0 \in Q$).

F

is the set of final states, $F \subseteq Q$.

For each symbol scanned, a TM:

1.

changes state,

2.

prints a symbol on tape cell, replacing what was written there before, and

3.

moves the tape head left or right one cell.