\begin{frame}{Extensions of Turing Machines}

  Extensions of TMs such as 
  \begin{itemize}\setlength{\itemsep}{0ex}
    \item multiple tapes, or
    \item nondeterminism
  \end{itemize}
  do \emph{not} give extra expressive power.
  \pause\medskip
  
  \begin{goal}{}
    \emph{Multiple tapes} can be simulated using a single tape with polynomial overhead in time complexity.
  \end{goal}
  \pause\medskip
  
  \begin{block}{}
    \emph{Nondeterministic Turing machines} have as transition function
    \begin{talign}
      \delta:Q\times\Gamma\rightarrow 2^{Q\times\Gamma\times\{L,R\}}
    \end{talign}
  \end{block}
  \pause
  
  \begin{goal}{}
    A nondeterministic TM can be simulated by deterministic TM using \emph{breadth-first search} (all computations in parallel).
    \medskip
    
    The overhead in \emph{time complexity} is believed to be an \emph{exponential factor}.
  \end{goal}
\end{frame}