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