7/40
\begin{frame}
  \small

  \begin{definition}
  A Turing machine $\langle Q, q_0, F, \Sigma, \Box, \delta \rangle$ is said to \alert{halt on $w = a_1 a_2\ldots a_n \in \Sigma^*$} 
  if it reaches a final state when started on the configuration:
  \smallskip
  
  \turing{\Box,\Box,\Box,a_1,\ldots,a_n,\Box}{q_0}{0}
  
  The tape content upon reaching the final state is called \alert{output}.
  \end{definition}
  \medskip\pause
  
  \begin{definition}[Decidable Problems]
  A predicate $P \subseteq \NN^d$ is \alert{decidable} if there is a Turing machine $M$ such that:
  \begin{itemize}
    \item $M$ terminates on all inputs $s^{n_1}0\; \cdots s^{n_d}0$ for $\langle n_1,\ldots,n_d \rangle \in \NN^d$, and
    \item $M$ halts with output $0$ if and only if $\langle n_1,\ldots,n_d \rangle \in P$. 
  \end{itemize} 
  \end{definition}
\end{frame}