\documentclass{article}

\usepackage[french]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
%\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{fullpage}

\usepackage{theorem}
\theorembodyfont{\rmfamily}
\newtheorem{exo}{Exercice}[section]

\newcommand{\Nat}{\mathbb{N}}
\newcommand{\seq}[2]{#1_1,\dots,#1_{#2}}
\newcommand{\funcname}[1]{\mathord{\mathrm{#1}}}
\newcommand{\Cod}{\funcname{Cod}}

\begin{document}

\section{Exercices sur les fonctions récursives}  
\subsection{Exercices sur les fonctions récursives primitives}  

\begin{exo}
  Soit $g:\Nat^3 \mapsto\Nat$ une fonction primitive récursive.  Soit $h
  :\Nat^4\mapsto\Nat$ définie par $h(x, y, z, u) = g (x, y, z)$ et $k : \Nat^3
  \mapsto \Nat$ définie par $k(x, y, z) = g (z, y, x)$.  Montrer que h et k
  sont primitives récursives. Généralisation~? Conclusion~?
\end{exo}

\begin{exo}
  On suppose que $h:\Nat^2\mapsto\Nat$ et $k:\Nat\mapsto\Nat$ sont des
  fonctions p.r., $a\in\Nat$. Soient $f : \Nat \mapsto \Nat$ définie par $f(0)
  = a$, $f(n+1) = h(n, f(n))$ et $g : \Nat\mapsto \Nat$ définie par $g(0) = a$
  et $g(n+1) = k (g (n))$. Les fonctions $f$ et $g$ sont-elles récursives
  primitives~?
\end{exo}

\begin{exo}
  Montrer que les fonctions suivantes sont p.r.~:
  \begin{enumerate}   
  \item $\funcname{Id}(x) = x$~;
  \item $\funcname{Add}(x, y) = x+y$~;   
  \item $\funcname{Mult}(x, y) = x . y$~;   
  \item $C_k(x) =  k$  (k  fixé)~;   
  \item $!(x) = 1.2 .... x$~;
  \item $(f + g) (x) = f (x) + g (x)$ où f et g sont p.r.
  \item $f*g (x)  = f (x) . g (x)$ où f et g sont p.r.
  \item $\funcname{Exp}(x, y) = x^{y}$~;
  \item $\funcname{Pred}(x)=
    \begin{cases}
      0   & \text{si $x = 0$},\\
      x-1 & \text{sinon}.
    \end{cases}$
  \item $\funcname{Moins}(x, y) =
    \begin{cases}
      0   & \text{si $x \leq y$},\\
      x-y & \text{sinon}. 
    \end{cases}$
  \item $\funcname{Zero}(x) =
    \begin{cases}
      0 & \text{si $x = 0$},\\
      1 & \text{sinon}.
    \end{cases}$
  \item $\funcname{nonzero}(x) =
    \begin{cases}
      0 & \text{si $x \neq 0$},\\
      1 & \text{sinon}.
    \end{cases}$
  \item $\funcname{Kr}(x, y) =
    \begin{cases}
      1 & \text{si $x = y$}, \\
      0 & \text{sinon}.
    \end{cases}$
  \end{enumerate}
\end{exo}

\begin{exo}
  Soit $R$ une relation $n$-aire. Notons $\chi_R$ sa fonction caractéristique
  usuelle, définie par~:
  \begin{displaymath}
    \chi_R(\seq x n) =
    \begin{cases}
      1 & \text{si $(\seq x n) \in R$}, \\
      0 & \text{sinon}.
    \end{cases}
  \end{displaymath}
  \begin{enumerate}
  \item Soit $g_R\:$ définie par : $g_R (\seq x n) =0$ si $(\seq x n)\in
    R$, 1 sinon.  Est-ce-que $\chi_R$ est récursive primitive ssi $g_R$
    est récursive primitive~?
  \item Soit $h_R$ une fonction totale vérifiant $h_R(\seq x n) = 0$ ssi
    $(\seq x n) \in R$.  Est-ce-que $\chi_R$ est récursive primitive
    ssi $h_R$ est récursive primitive~?
  \end{enumerate}
\end{exo}

\begin{exo}
  Les relations sur $\Nat^2$ suivantes sont-elles récursives primitives~?
  $\leq$, $<$, $\geq\:$, $>$, $=$.
\end{exo}

\begin{exo}
  Soit $R$ une relation $n$-aire récursive primitive, $\seq f n$ des fonctions
  récursives primitives. Montrer que~: $R(f_1(\seq x n ), \dots, f_n(\seq x n
  )$) est une relation récursive primitive.
\end{exo}

\begin{exo}
  Soit $R(\seq x n, x)$ et $f(\seq x n)$ une relation et une fonction p.r.
  Montrer que : $S(\seq x n) \equiv \forall x \leq f(\seq x n), R(\seq x n ,
  x)$ et que $S(\seq x n) \equiv \exists x \leq f(\seq x n), R(\seq x n , x)$
  sont p.r.
\end{exo}

\begin{exo}
  Les fonctions ou relations suivantes sont-elles récursives primitives~?
  \begin{enumerate} 
  \item $D(x,y) =
    \begin{cases}
      \text{partie entière de $x/y$} & \text{si $y\neq 0$},\\
      0                              & \text{sinon}.
    \end{cases}$
  \item $\surd x = \text{partie entière de $\sqrt x$}$~;
  \item $\sum(x) = 0 + 1 + 2 + \cdots x$~:
  \item la relation $\funcname{Div}(x,y)$~: <<~$x$ divise $y$~>>~;
  \item les prédicats <<~$x$ est pair~>>, <<~$x$ est impair~>>, <<~$x$
    est premier~>>, <<~$x$ est un nombre magique (égal à la somme de ses
    diviseurs)~>>~;
  \item $f :\Nat\mapsto\Nat$ définie par~:
    $f(x) =  2x$  si $x$ est un carré, $2x + 1$ sinon~;
  \item $g : \Nat\mapsto\Nat$ définie par~: $g(x) = $ la somme de ses
    diviseurs si $x \neq 0$, $0$ sinon~;
  \item $\Pi(x) = $ le nombre de nb premiers $\leq x$~;
  \item  La relation <<~$x$ est la somme de 2 carrés~>>~;
  \item  $f : \Nat\mapsto\Nat$ telle que~: $f(n) = $ le n-ième nombre premier~:
  \item  $h : \Nat\mapsto\Nat$ définie par $h(x) = \surd 2 x$.
  \end{enumerate}
\end{exo}

\begin{exo}
  Soient $f, g, h : \Nat^n \mapsto \Nat$ des fonctions p.r.  Est-ce-que $k :
  \Nat^n \mapsto\Nat$ définie par~:
  \begin{displaymath}
    k (\seq x n)=
    \begin{cases}
      f (\seq x n) & \text{si $h (\seq x n) = 0$},\\ 
      g(\seq x n) & \text{sinon} 
    \end{cases}
  \end{displaymath}
  est p.r.~?
\end{exo}

\begin{exo}
  Soit $f$ une fonction p.r., $k$ un entier non nul, $\seq a k$ des entiers.
  Les fonctions $g$ et $h$ définies par~:
  \begin{itemize}
  \item $g (0) = a_0$, $g(1)  = a_1$, ..., $g(k) = a_k$ et $g(x)  =
    f(x)$ pour $x > k$~;
  \item $h(0) = a_0$, $h(1) = a_1$, ..., $h(k) = a_k$ et $h(n + 1) =
    f(h(n))$ pour $n > k$~;
  \end{itemize}
  sont elles p.r.~?
\end{exo}

\begin{exo}[Fonctions de codage]
  On dit qu'une fonction $g : \Nat^2\mapsto\Nat$ est une \emph{fonction de
    codage} si $g$ est bijective et croissante en chaque argument, c'est à
  dire~: $\forall x, y, g(x,y) < g(x+1,y) \text{ et } g(x,y) < g(x,y+1)$.
  \begin{enumerate}
  \item Décider si les fonctions ci-dessous sont des
    fonctions de codage.

    \begin{itemize} 
    \item $g_1(x,y)= 2^x . (2y+1) - 1$~;
    \item $g_2(x,y)= 2^x . 3^{y.x}$~;
    \item $g_3(x,y)= (x+y) (x+y+1)/2 + y$~;
    \item $g_4(x,y)= (E((x+1)/2 + y)^2 + x$ ($E(x)$ est la partie entière
      de $x$).
    \end{itemize}

  \item Pour chaque fonction de codage trouvée : 
    \begin{enumerate} 
    \item définir les fonctions réciproques (appelées aussi fonction de
      décodage) $\pi _1$ et $\pi _2$ vérifiant $g(\pi_1(x), \pi_2(x)) = x$~;
    \item la fonction $g_i$ et ses réciproques sont-elles p.r.~?
    \end{enumerate}
  \end{enumerate}
\end{exo}

\begin{exo}
  On appelle \emph{fonction de Fibonacci} la fonction $F : \Nat\mapsto\Nat$
  définie par~: $F(0) = F(1) = 1$ ; $F(n+2) = F(n+1) + F(n)$. Montrer que la
  fonction de Fibonacci est récursive primitive.
\end{exo}

\begin{exo}
  A l'aide d'une fonction de codage $C:\Nat ^2\mapsto\Nat$, et des fonctions de
  décodage $\pi _1$ et $\pi _2$, montrer que l'on peut définir des fonctions de
  codage entre $\Nat$ et $\Nat^m$ pour $m \geq 2$.
\end{exo}

\begin{exo}
  Soit $A = \{\seq a k\}$ un ensemble à k éléments ($A$ est appelé un
  alphabet). Soit $A^*$ l'ensemble des suites finies d'éléments de $A$ (on dit
  qu'un élément $m$ de $A^*$ est un mot de $A$, il sera noté :
  $m=a_{i_1}a_{i_2}\dots a_{i_p}$~; quand $p=0$, on dit que $m$ est le mot vide
  et on le note $\epsilon$).

  Soit l'application $\Cod : A^*\mapsto \Nat$, définie par
  $\Cod(\epsilon ) = 0$,  $\Cod(x_1 x_2 \cdots x_n ) = \sum_{i = 1}^n
  (j_i) k^{i-1}$ (où $j_i$ est l'indice tel que $a_{j_i} = x_i$)
  \begin{enumerate}
  \item Pour $k=3$, calculer $\Cod(a_3a_1a_3a_2a_3)$ et
    $\Cod(a_1a_3a_3a_3a_2)$.
  \item Comparer $n= \Cod(\seq x n)$ et l'écriture en base 3 de $n$.
  \item Décoder $n= 441$.
  \item Décrire les algorithmes de codage et décodage.
  \item En déduire que $\Cod$ est bijective. 
  \end{enumerate}
\end{exo}

\subsection{Exercices sur les fonctions partielles récursives}

\begin{exo}
  Un entier $p$ est appelé double-premier si $p$ et $p-2$ sont premiers. Il est
  largement admis mais non prouvé qu'il y a une infinité de double-premiers.

  Soit $T$ la fonction sur $\Nat$ définie par : $T(n)$ est le $n$-ième
  nombre double premier.

  Montrer que $T$ est une fonction partielle récursive (totale si la
  conjecture est vraie).
\end{exo}

\begin{exo}[La fonction d'Ackermann]
  Soit $A : \Nat^2 \mapsto\Nat$ la fonction définie par~:
  \begin{align*}
    A (0, p) &= p + 1\\
    A (n + 1, 0) &= A (n, 1)\\
    A (n + 1, p + 1) &= A (n, A (n + 1, p))
  \end{align*}
  Notons $A_n\:$ la fonction de $\Nat\mapsto \Nat$
  définie par $A_n(p) = A(n, p)$.

  Démontrer les propriétés suivantes :
  \begin{enumerate}
  \item $A_0$, $A_1$, $A_2$ et $A_3$ satisfont~: $A_0(n) = n+1$,
    $A_1(n) = n+2$, $A_2(n) = 2n+3$ et $A_3(n) = k2^n +c$ (k et c à
    déterminer).
  \item $\forall n,\forall x, A_n(x) > x$.
  \item Pour tout $n$ les fonctions $A_n$ sont strictement croissantes.
  \item $\forall n, \forall x,  A_{n+1}(x) \geq A_n(x)$.
  \item $\forall n, \forall x,  A_{n+1}(x) \geq A_n(x+1)$
  \item $\forall n_1, \forall n_2, \exists m, \forall x, A(n_1, A(n_2,
    x)) \leq A(m,x)$.
  \item $\forall n_1, \forall n_2, \exists m,  \forall x, A(n_1, x)
    + A(n_2, x) \leq A(m,x)$.
  \item Soient $m$ un entier et $f$ une fonction~; on dira que $f$ est
    $m$-bornée ssi
    \begin{displaymath}
      \forall \seq xp, f(\seq xp) \leq A(m,  x_1 + \cdots + x_p )
    \end{displaymath}

    Si l'on note $\mathcal{M} = \{f\text{ telle que } \exists m, f \text{ est
      $m$-bornée} \}$, montrer que $\mathcal{M}$ contient l'ensemble
    des fonctions récursives primitives.
  \item En déduire que A n'est pas récursive primitive.
  \end{enumerate}
\end{exo}
\end{document}
