\begin{frame}{Universal Turing Machine}
  A computer can execute any program on any input.
    A TM is called \emph{universal} if it can simulate every TM.
    A universal TM gets as input
      \item a Turing machine $M$ (described as a word $w$),
      \item an input word $u$,
    and then executes (simulates) $M$ on $u$.

  These two inputs can either
    \item be written on two different tapes, or
    \item be written behind each other ($w\#u$) on one tape.

    There exists a universal Turing machine.