15/113
\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}
  \medskip\pause

  These two inputs can either
  \smallskip
  \begin{itemize}
    \item be written on two different tapes, or
    \item be written behind each other ($w\#u$) on one tape.
  \end{itemize}
  \medskip\pause

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