\begin{frame}{Space Complexity}
  Let $f,g : \mathbb{N} \to \mathbb{N}$.

  \begin{block}{}
    A nondeterministic Turing machine $M$ 
    \begin{center}
      \emph{runs in space} $f$
    \end{center}
    if for \alert{every input $w$}, every computation of $M$ 
    visits \alert{at most $f(|w|)$ positions on the tape}.
  \end{block}
  \pause\medskip
  
  \begin{goal}{}
    The function $f$ gives an upper bound on the number of visited cells on the tape
    in terms of the length of the input word.
  \end{goal}
\end{frame}