From 946d5d532b22cf44e8a9cc98c9daf11952ab966d Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 17 Oct 2023 11:39:05 +0200
Subject: Tiding of things to come.

---
 transp-inf110-01-calc.tex | 43 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 43 insertions(+)

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
@@ -367,6 +367,49 @@ préfèrent $f(n) \simeq g(m)$ pour ça.)
 \itempoint Terminologie : une fonction $f\colon \mathbb{N} \to
 \mathbb{N}$ est dite \textbf{totale}.
 
+\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}
-- 
cgit v1.2.3