Tiding of things to come.

1 files changed, 43 insertions, 0 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 9db3669..76543df 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -369,6 +369,49 @@ préfèrent $f(n) \simeq g(m)$ pour ça.)
 
 \end{frame}
 %
+\begin{frame}
+\frametitle{Terminologie à venir (avant-goût)}
+
+\itempoint Une fonction partielle $f\colon \mathbb{N} \dasharrow
+\mathbb{N}$ est dite \textbf{calculable} (partielle) lorsqu'il existe
+un algorithme qui prend $n$ en entrée et :
+\begin{itemize}
+\item termine (en temps fini) et renvoie $f(n)$ lorsque $f(n)\downarrow$,
+\item ne termine pas lorsque $f(n)\uparrow$.
+\end{itemize}
+
+\bigskip
+
+\itempoint Une partie $A \subseteq \mathbb{N}$ est dite
+\textbf{décidable} lorsque sa fonction indicatrice
+$\mathbb{N}\to\mathbb{N}$
+\[
+\mathbf{1}_A\colon n \mapsto \left\{
+\begin{array}{ll}
+1&\text{~si $n\in A$}\\
+0&\text{~si $n\not\in A$}\\
+\end{array}
+\right.
+\]
+est calculable (répondre « oui » ou « non » selon que $n\in A$ ou $n\not\in A$).
+
+\bigskip
+
+\itempoint Une partie $A \subseteq \mathbb{N}$ est dite
+\textbf{semi-décidable} lorsque sa fonction « semi-indicatrice »
+$\mathbb{N}\dasharrow\mathbb{N}$ (d'ensemble de définition $A$)
+\[
+n \mapsto \left\{
+\begin{array}{ll}
+1&\text{~si $n\in A$}\\
+\uparrow&\text{~si $n\not\in A$}\\
+\end{array}
+\right.
+\]
+est calculable (répondre « oui » ou « ... » selon que $n\in A$ ou $n\not\in A$).
+
+\end{frame}
+%
 \section{Fonctions primitives récursives}
 \begin{frame}
 \frametitle{Fonctions primitives récursives : définition}