\begin{frame}{Turing Machines} \begin{goal}{} A \emph{deterministic Turing machine}, short TM, is a 7-tuple \begin{talign} (Q,\Sigma,\Gamma,\delta,q_0,\Box,F) \end{talign} where \begin{itemize} \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. \end{itemize} \end{goal} \pause \begin{block}{} \emph{Assumption}: $\delta(q,a)$ is undefined for every $q\in F$ and $a\in\Gamma$. \end{block} So the computation stops when reaching a final state. \end{frame}