Tape Machine
Definition
A tape machine (or
Turing machine) is a list
\[
M = (Q, \Sigma , \Gamma , b, \delta , q_0, q_{\text{accept}},
q_{\text{reject}})
\]
where $Q$ is a finite set, $\Sigma $ is an
alphabet with $b \not\in \Sigma $, $\Gamma $ is
an alphabet with $\Sigma \subset \Gamma $ and
$b \in \Gamma \setminus \Sigma $,
\[
\delta : Q \times \Gamma \to Q \times \Gamma \times
\{-1, -1\}
\]
is a function and $q_0, q_{\text{accept}},
q_{\text{reject}} \in Q$ with $q_{\text{accept}}
\neq q_{\text{reject}}$.
