11/113
\begin{frame}{Nondeterministic Turing Machines}
A \alert{nondeterministic} Turing machine has as transition function
\begin{talign}
\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}
\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}