TD6 : Fonctions récursives

EX 1

Fonction prédécesseur : $Pred$

\[Pred = Prim(Z, 𝜋_2^2)\]

• Soustraction $Sous$ de $a$ par $b$ :
  • \[-Sous(a,b) = \begin{cases} a \text{ si } b=0 \\ Pred(Sous(a,b-1)) \text{ sinon} \end{cases}\]
  • \[Sous = Comp(Prim(𝜋_2^2, Comp_4(Pred, 𝜋_4^1)),𝜋_2^2, 𝜋_2^1)\]
• Égalité :
  • $=_0$ = true pour 0, false sinon
    • \[=_0 = Prim(Comp_1(S,Z), Comp_1(Z, 𝜋_3^1))\]
  • Or, comme il n’y a pas de nombres négatifs ($Pred(0)=0$): \(Sous(a,b)=0 ⟺ b≥a\)
  • \[Egalité = (=_0( Sous(a,b))) ∧ (=_0( Sous(a,b)))\]
• \[Even(n) = \begin{cases} 1 \text{ si } n=0 \\ 1-Even(n-1) \text{ sinon} \end{cases}\]
• \[div_2(n) = \begin{cases} 0 \text{ si } n=0 \\ Even(n)×(1+div_2(n-2)) + (1-Even(n))×div_2(n-1) = Even(n) + div_2(n-1) \text{ sinon} \end{cases}\]

EX2

\[MinEstAvant(l, \vec{n}) = \begin{cases} 1 \text{ si } ∃m≤l; 𝜉(m,\vec{n})=0 \\ 0 \text{ sinon} \end{cases} \\ = \begin{cases} 1-𝜉(0,\vec{n}) \text{ si } l=0 \\ MinEstAvant(l-1, \vec{n}) + (1-MinEstAvant(l-1, \vec{n}))(=_0(𝜉(l,\vec{n}))) \text{ sinon} \end{cases}\] \[𝜃(m,\vec{n}) = \begin{cases} 1 - =_0(𝜉(0,\vec{n})) \text{ si } m = 0 \\ MinEstAvant(m, \vec{n}) 𝜃(m-1, \vec{n}) + (1-MinEstAvant(m, \vec{n}))×m×(=_0(𝜉(m,\vec{n})) \text{ sinon} \end{cases}\] \[𝜙(\vec{n}) = 𝜃(𝜓(\vec{n}), \vec{n})\]

EX3

\[J = \begin{cases} ℕ^2 ⟶ ℕ \\ (x,y)\mapsto 2^x(2y+1) -1 \end{cases}\]

bijection

\[2^n = \begin{cases} 1 \text{ si } n=0 \\ 2× 2^{n-1} \text{ sinon} \end{cases}\] \[K = \begin{cases} ℕ ⟶ ℕ^2 \\ 2^x(2y+1) -1 \mapsto div_2(2^n z) \text{ où } n ≝ \min\limits_{m≤z} \{(z+1)/2^m \text{ est impair}\} \end{cases}\] \[L(2^x(2y+1) -1) = \frac{z+1}{2^{K(z)}}\] \[div_2(2^n z)=\begin{cases} div_2(z) \text{ si } n=0 \\ 2^{n-1} z \text{ sinon} \end{cases}\] \[𝜑(n, x) = \begin{cases} J(g(n),0) \text{ si } x=0 \\ J(h(K(𝜑(n-1,n), L(𝜑(n-1, n) +1))), L(𝜑(n-1, n)+1)) \text{ sinon} \end{cases}\]