\begin{frame}{Universal Turing Machine}
  
  A computer can execute any program on any input.
  \medskip\pause
  
  \begin{goal}{}
    A TM is called \emph{universal} if it can simulate every TM.
    \medskip
    
    A universal TM gets as input
    \begin{itemize}
      \item a Turing machine $M$ (described as a word $w$)
      \item an input word $u$
    \end{itemize}
    and then executes (simulates) $M$ on $u$.
  \end{goal}
  The input $w$ and $u$ can be written on the tape as $w\#u$.
  \medskip\pause

  \begin{block}{Theorem}
    There exists a universal Turing machine.
  \end{block}  
\end{frame}