Languages
$A = \{ 0 , 1 \}$: Alphabet, finite set.
$A^* = \{ \epsilon , 0 , 1 , 00, 01, 10, 11, 000, \ldots \}$: Kleene star of $A$.
$L \subseteq A^*$: Language.
Turing machine
$M = (A, A’, \square, S, Y, N, s_0, \delta)$.
$A$: input alphabet.
$A’ \supset A:$ tape alphabet.
$\square \in (A’ \setminus A)$: blank symbol, not in $A$.
$S$: finite set of states.
$Y \in S$: accept state.
$N \in S$: reject state.
$s_0 \in S$: initial state.
$\delta:(A’ \times (S \setminus \{-1, 1\})$$ \rightarrow $$(A’ \times S \times \{L,R\}):$ transition function.
Language of a machine
$x \in A^*$: accepted iff $\delta$ repeatedly applied to $x$ ends in $Y$.
$L(M) = \{x \in A^* | x \textrm{ accepted by } M\}$.