Definitions

We will use a flow graph notation to specify Turing machines; see the scheme used in Turing's World. (As explained in class, we will use the quadruple, rather than the quintuple, formalism.) In the background, however, stands a fully formal set theoretic definition, according to which a Turing machine is a quadruple $(S, \Sigma, f, s)$ where

1.

S is a finite set of states;

2.

$\Sigma$ is an alphabet containing the black symbol -, but not containing the symbols $\Leftarrow$ (``go left") and $\Rightarrow$ (``go right").

3.

$s \in S$ is the initial state;

4.

$f : S \times \Sigma \longrightarrow (\Sigma \cup \{\Leftarrow, \Rightarrow\}) \times S$ (the transition function).