From 3cca962ef3d7dba54756b3ae11556d09cca61839 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Wed, 18 Oct 2023 10:28:23 +0200
Subject: Remove flawed part about eliminating recursivity.

---
 transp-inf110-01-calc.tex | 105 ----------------------------------------------
 1 file changed, 105 deletions(-)

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 9aeeb71..8f1c3e6 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -977,111 +977,6 @@ f(\underline{x},z+1) &= h(\underline{x},f(\underline{x},z),z)
   \mathbb{N}^k \dasharrow \mathbb{N}$ est récursive.
 \end{itemize}
 
-\end{frame}
-%
-\begin{frame}
-\frametitle{Élimination de la récursivité}
-
-Considérons une définition récursive du type (ceci n'est qu'un exemple) :
-\[
-f(x) = \left\{
-\begin{array}{ll}
-g(x)&\text{~si~}t(x)=0\\
-h(x,f(v(x)))&\text{~si~}t(x)\neq 0\\
-\end{array}
-\right.
-\]
-à comprendre comme l'algorithme évident
-
-{\footnotesize\texttt{f(x) \{ if (t(x)==0) \{ return g(x); \} else \{
-    return h(x,f(v(x))); \} \}}\par}
-
-Comment voir que $f$ est générale récursive (si $t,g,h,v$ le sont) ?
-
-\bigskip
-
-\itempoint On définit une version avec un paramètre $N$ supplémentaire
-(« profondeur de pile d'appels », « quantité essence ») :
-\[
-\begin{aligned}
-\tilde f(0,x) &= 0\\
-\tilde f(N+1,x) &= \left\{
-\begin{array}{ll}
-g(x)&\text{~si~}t(x)=0\\
-h(x,\tilde f(N,v(x)))&\text{~si~}t(x)\neq 0\\
-\end{array}
-\right.\\
-\end{aligned}
-\]
-et une fonction indiquant s'il faut plus de profondeur
-\[
-\begin{aligned}
-w(0,x) &= 1\\
-w(N+1,x) &= \left\{
-\begin{array}{ll}
-0&\text{~si~}t(x)=0\text{,~ou~bien~}t(x)\neq 0\text{~et~}w(N,v(x))=0\\
-1&\text{~sinon}
-\end{array}
-\right.\\
-\end{aligned}
-\]
-
-\end{frame}
-%
-\begin{frame}
-\frametitle{Élimination de la récursivité (suite)}
-
-Plus général\textsuperscript{t}, on transforme une fonction récursive
-$f$ en $\tilde f$ avec un argument « profondeur » supplémentaire, avec
-$\tilde f(0,\ldots)$ arbitraire, et chaque appel de $\tilde
-f(N+1,\ldots)$ faisant faisant appel à $\tilde f(N,\ldots)$ dans la
-récursion.  Quant à $w(N+1,\ldots)$ il vaut $0$ si tous les appels à
-$\tilde f(N,\ldots)$ ont $w(N,\ldots)=0$, et $1$ sinon.
-
-\medskip
-
-Alors :
-\begin{itemize}
-\item $\tilde f$ et $w$ sont définis par récursion primitive,
-\item $f(\underline{x}) = \tilde f(\mu w(\underline{x}), \underline{x})$
-\end{itemize}
-
-\end{frame}
-%
-\begin{frame}
-\frametitle{Élimination de la récursivité (exemple)}
-
-Exemple : la \textbf{fonction d'Ackermann} est définie par :
-{\footnotesize
-\[
-\begin{aligned}
-A(m,n,0) &= m+n \\
-A(m,1,k+1) &= m \\
-A(m,n+1,k+1) &= A(m,\,A(m,n,k+1),\,k)
-\end{aligned}
-\]
-\par}
-
-On transforme cette définition récursive en une définition par $\mu$ :
-
-{\footnotesize
-\[
-\begin{aligned}
-\tilde A(0,m,n,k) &= 0 \\
-\tilde A(N+1,m,n,0) &= m+n \\
-\tilde A(N+1,m,1,k+1) &= m \\
-\tilde A(N+1,m,n+1,k+1) &= \tilde A(N,m,\,\tilde A(N,m,n,k+1),\,k)\\
-w(0,m,n,k) &= 1 \\
-w(N+1,m,n,0) &= 0 \\
-w(N+1,m,1,k+1) &= 0 \\
-w(N+1,m,n+1,k+1) &= w(N,m,n,k+1) \;\vee\; w(N,m,\,\tilde A(N,m,n,k+1),\,k)\\
-A(m,n,k) &= \tilde A(\mu w(m,n,k), m,n,k)
-\end{aligned}
-\]
-\par}
-
-Ici $\tilde A$ et $w$ \alert{sont p.r.} et $A$ est générale récursive.
-
 \end{frame}
 %
 \end{document}
-- 
cgit v1.2.3