\begin{frame}{Turing Machines are Recursively Enumerable}
  \begin{goal}{Theorem}
    Turing machines are recursively enumerable.
  \end{goal}
  \pause

  \begin{proof}
    \begin{itemize}
      \item A Turing machine can be represented as a word.
      \item A parser can check whether a word represents a TM.\\
        (If so, accept.)
    \end{itemize}
  \end{proof}
  \pause
    
  Thus, there is a recursive enumeration of all Turing machines:
  \begin{talign}
    M_1, M_2, \ldots
  \end{talign}
  \pause
  Formally, we enumerate words describing Turing machines.
  But the does not matter since we have a universal Turing machine that can execute these descriptions.
\end{frame}
  
\themex{Properties of Recursively Enumerable Languages}