\begin{frame}{Turing Machines are Recursively Enumerable}
    Turing machines are recursively enumerable.

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