\begin{frame}{Recursively Enumerable Languages}
  \begin{block}{}
    A language $L$ is \emph{recursively enumerable} if
    $L$ is accepted by a (deterministic) Turing machine.
  \end{block}
  \pause\medskip
  
  \begin{goal}{}
    Equivalently, a language $L$ is recursively enumerable 
    if there exists a Turing machine \emph{enumerates all words} in $L$.
  \end{goal}
  \pause
  Intuitively, the Turing machine writes on the tape
  \begin{talign}
    \# w_1 \# w_2 \# w_3 \# \cdots
  \end{talign}
  such that $L = \{\, w_1,w_2,w_3,\ldots \,\}$.
  \pause\medskip
  
  If $L$ is infinite, this computation never stops!
  Every word from $L$ will eventually be written on the tape.
  \pause
  
  \begin{goal}{}
    Then $w_1,w_2,\ldots$ is called a \emph{recursive enumeration} of $L$.
  \end{goal}
\end{frame}