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}