\begin{frame}{Turing Machines}
    A \emph{deterministic Turing machine}, short TM, is a 7-tuple 
      \item \alert{$Q$} is a finite set of states,
      \item $\alert{\Sigma} \subseteq \Gamma \setminus \{\,\Box\,\}$ a finite input alphabet,
      \item \alert{$\Gamma$} a finite tape alphabet,
      \item $\alert{\delta} : Q \times \Gamma \to Q \times \Gamma \times \{\,L,R\,\}$ a partial transition function,
      \item \alert{$q_0$} the starting state,
      \item $\alert{\Box} \in \Gamma$ the blank symbol,
      \item $\alert{F} \subseteq Q$ a set of final (accepting) states.
    \emph{Assumption}: $\delta(q,a)$ is undefined for every $q\in F$ and $a\in\Gamma$.
  So the computation stops when reaching a final state.