12/15
\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}