\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}