Computability

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