\begin{frame}{Turing Machines and Languages}
  \begin{block}{}
    The \emph{language $L(M)$} accepted by TM $M = (Q,\Sigma,\Gamma,\delta,q_0,\Box,F)$ is 
    \begin{talign}
      \{\, w \in \Sigma^* ~\mid~  q_0 w  \vdash^* u q v \;\text{ for some $q \in F,~u,v \in \Gamma^*$}\,\}
    \end{talign}
  \end{block}
  \pause

  If $w \not\in L(M)$ this can have two causes:
  \begin{itemize}\setlength{\itemsep}{0pt}
    \item the execution halts in a configuration $vqw$ with $q \not\in F$, or
    \item the execution is infinite (never halts).
  \end{itemize}
  \pause

  \begin{exampleblock}{}
    \begin{minipage}{.64\textwidth}
      \begin{center}
        \begin{tikzpicture}[default,node distance=25mm,->,s/.style={minimum size=5mm}]
          \node (q0) [state,s] {$q_0$}; \draw ($(q0) + (-8mm,0mm)$) -- (q0); 
          \node (q1) [state,s,right of=q0] {$q_1$};
          \node (q2) [fstate,s,right of=q1] {$q_2$};
        
          \draw (q0) to[bend left=20] node [label,above] {$a/b$ $R$} (q1);
          \draw (q0) to[tloop] node [label,above] {$b/a$ $R$} (q0);
          \draw (q1) to[bend left=20] node [label,below] {$a/b$ $R$} (q0);
          \draw (q1) to[tloop] node [label,above] {$b/a$ $R$} (q1);
          \draw (q1) to node [label,above] {$\Box/\Box$ $L$} (q2);
        \end{tikzpicture}
      \end{center}
    \end{minipage}%
    \begin{minipage}{.35\textwidth}
      What is $L(M)$?
      \pause\medskip
      
      The set of words over $\Sigma = \{\,a,b\,\}$
      with an odd number of $a$'s.
    \end{minipage}
  \end{exampleblock}
  \pause\medskip
  
  \begin{goal}{}
    A language is \emph{recursively enumerable} if it is accepted by a TM.\!\!
  \end{goal}
\end{frame}