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