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}

Leave a comment