11/113
\begin{frame}{Nondeterministic Turing Machines}
  A \alert{nondeterministic} Turing machine has as transition function
  \begin{talign}
    \alert{\delta:Q\times\Gamma\rightarrow 2^{Q\times\Gamma\times\{L,R\}}}
  \end{talign}
  \vspace{-2ex}
  \pause
  \begin{block}{Theorem}
    A nondeterministic TM can be simulated by a deterministic TM.
  \end{block}
  \pause
  
  \begin{proof}
    The deterministic TM can use 
    \begin{itemize}
      \item \emph{breadth-first search}
    \end{itemize}
    to simulate all executions of the nondeterministic TM in parallel.\\
    \medskip
    
    The branches of the breadth-first search can be stored 
    on the tape in the form \emph{queue}.
  \end{proof}
  \pause
    
  \begin{goal}{}
    The difference in \emph{time complexity} between nondeterministic and deterministic TM
    is, as far as known, an \emph{exponential} factor.\!
  \end{goal}
\end{frame}