diff options
| -rw-r--r-- | transp-inf110-01-calc.tex | 43 |
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} |