11/55

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