\begin{frame}{Central Question: What can a Computer do?} \medskip \emph{What can a computer do?} \pause\medskip \begin{goal}{} Some (at first glance simple) problems are \alert{undecidable}. \end{goal} \smallskip For example: \begin{itemize}\setlength{\itemsep}{.0ex} \item program termination \item Post correspondence problem \item validity in predicate logic \end{itemize} \pause\medskip \begin{minipage}{.65\textwidth} \begin{goal}{} Some problems (\alert{NP-hard problems}) are (probably) not efficiently solvable by a computer. \end{goal} \smallskip For example: \begin{itemize}\setlength{\itemsep}{.0ex} \item travelling salesman problem \item satisfiability in propositional logic \end{itemize} \end{minipage} \begin{minipage}{.34\textwidth} \hfill \includegraphics[height=3cm]{images/salesman.jpg} \end{minipage} \vspace{10cm} \end{frame}