7/113
\begin{frame}{Turing Machines with Multiple Tapes}
  \begin{block}{Theorem}
    A TM with two tapes can be simulated by 
    a TM with one tape.
  \end{block}
  \pause
  
  \begin{exampleblock}{}
    Consider \alert{$\delta(q,a,d)=(q',g,h,L,R)$}
    \vspace{-2mm}
    
    \begin{center}
    \input{tweetapes.pdf_t}
    \end{center}
    \pause\vspace{-3mm}
    The transition translates to multiple transitions on one tape:
    \vspace*{-3mm}
    
    \begin{center}
    \input{tweetapes2.pdf_t}
    \end{center}
  \end{exampleblock}
  \pause
  
  \begin{goal}{}
    The difference in \emph{time complexity} between a Turing machine
    with one tape and multiple tapes is a \emph{polynomial} factor.
  \end{goal}
\end{frame}