Université Paris Diderot Année 2016–2017

UFR de mathématiques Logique et complexité

TD 1 – Fonctions récursives primitives

Exercice 1.
Montrer que pour tout n ∈ N l’ensemble {n} est récursif primitif. En déduire que tout sous-ensemble de N qui
est fini ou qui est le complémentaire d’un sous-ensemble fini de N est récursif primitif.

Solution de l’exercice 1.
On va montrer que les singletons sont récursifs primitifs car leur fonction caractéristique est récursive primitive.
On sait que l’égalité f définie par f (x, y) = 1 si x = y et 0 sinon est récursive primitive. Si on note cn la fonction
constante égale à n à une variable, on a χ{n} = f (π11 , cn ) ce qui montre que {n} est bien un ensemble récursif
primitif.
L’ensemble des ensembles récursifs primitifs étant clos par opérations booléennes, un sous ensemble fini de N
est la réunion de singletons de N qui sont récursifs primitifs et donc est récursif primitif. De même les ensembles
cofinis de N sont récursifs primitif par passage au complémentaire.

Exercice 2.
Montrer que l’ensemble des nombres pairs est récursif primitif.

Solution de l’exercice 2.
La fonction caractéristique f des nombres pairs se définit de la manière suivante par récurrence : f (0) = 1 et
f (n + 1) = 1 − f (n) ; elle est donc bien récursive primitive.

Exercice 3.
Soit p un entier non nul. Montrer que la fonction supp : Np → N qui à (x1 , . . . , xp ) associe le maximum de
x1 , . . . , xp est récursive primitive.

Solution de l’exercice 3.
Soit p un entier non nul , on veut montrer que la fonction supp qui au p-uplet (x1 , . . . , xp ) associe le plus grand
des xi pour i appartenant à {1, . . . , p}. On fait une démonstration par récurrence sur p.

sup1 (x1 ) = x1 , sup1 = π11 (c’est la projection à un argument)

On suppose que les supi pour i appartenant à {1, . . . , p − 1}, sont récursives primitives on regarde pour supp+1 :

supp+1 (x1 , . . . , xp+1 ) = sup2 (supp (x1 , . . . , xp ), xp+1 )

où sup2 (x, y) = x si x > y et y sinon. Ainsi, supp+1 est récursive primitive.
Donc la fonction supp est récursive primitive pour tout p ∈ N∗ .

Exercice 4.
Montrer que les fonctions quotient et reste sont récursives primitives (par définition, on pose x/y = 0 si y = 0).
En déduire que {(x, y) | y divise x} est récursif primitif.

Solution de l’exercice 4.
Notons q la fonction quotient. On a q(x, y) = µk 6 x . (k + 1)y > x, donc q est récursive primitive. La fonction
reste est égale à r(x, y) = x − yq(x, y) l’est également.

Exercice 5.
Montrer que l’ensemble des nombre premiers est récursif primitif. En déduire que la fonction π qui à n fait
correspondre le (n + 1)-ième nombre premier est récursive primitive.

Solution de l’exercice 5.
Un entier n est premier ssi n > 1 et pour tout a ∈ {2, n − 1}, a ne divise pas n (qui peut s’écrire : pour tout
a < n, a < 2 ou a ne divise pas n). Ceci montre que l’ensemble des nombre premiers est récursif primitif.
La fonction f qui à n fait correspondre le (n + 1)-ième nombre premier est définie par récurrence : f (0) = 2 et
f (n + 1) = µa 6 (f (n)! + 1).(a > f (n) et a premier).

1
Exercice 6.
Soit f : N → N une fonction récursive primitive. Montrer que la fonction g définie par g(x) = f ◦ f ◦ . . . ◦ f (0)
| {z }
x+1 fois
est récursive primitive.

Solution de l’exercice 6. (
g(0) = f (0)
On définit g par schéma de récurrence : .
g(x + 1) = f (g(x))

Exercice 7. .x
..
Montrer que la fonction x 7→ xx , où le nombre de x dans la tour d’exponentielles est x + 1, est récursive
primitive.

Solution de l’exercice 7. .x
..
On définit d’abord par schéma de récurrence
( une fonction récursive primitive F (x, n) = xx , où le nombre de
F (x, 0) = 1
x dans la tour d’exponentielles est n : . La fonction cherchée est F (x, x), qui est donc
F (x, n + 1) = xF (x,n)
récursive primitive.

Exercice 8.
Soit E l’ensemble des entiers naturels qui sont la somme de deux carrés. Montrer que E est récursif primitif.

Solution de l’exercice 8.
x ∈ E s’exprime par ∃s, t 6 x (s2 + t2 = x).

Exercice 9.
Soit f : N → N définie par f (a, b) = α2 (c, d) où c/d est l’écriture simplifiée de la fraction a/b si b 6= 0, et
c = d = 0 sinon. Montrer que la fonction f est récursive primitive.

Solution de l’exercice 9.
Il existe plusieurs solutions. On peut par exemple définir f (a, b) comme le plus petit entier k ≤ α2 (a, b) tel que
β21 (k) · b = β22 (k) · a et k 6= 0.

Exercice 10.
Soit u la fonction qui à n ∈ N associe le (n + 1)-ième entier naturel (dans l’ordre croissant) qui est une somme
de deux carrés. Montrer que u est récursive primitive.

Solution de l’exercice 10.

( définit la fonction u par un schéma de récurrence :
On
u(0) = 0


u(n + 1) = µk 6 (u(n) + 1)2 . k > u(n) et ∃x, y 6 k (x2 + y 2 = k)

Exercice 11.
Soit f la fonction qui à n associe le nombre d’entiers premiers inférieurs ou égaux à n. Montrer que f est
récursive primitive.

Solution de l’exercice 11.

Deux solutions :
1. On utilise le test de primalité vu dans un exercice
Pn précédent : P (k) = 1 si k est premier et 0 sinon. Ce
test est récursif primitif. On a alors f (n) = k=0 P (k) qui est récursive primitive comme somme bornée
de fonctions récursives primitives.
( (
f (0) =0 y + 1 si P (n + 1) = 1
2. Par schéma de récurrence on pose : , avec h(n, y) = .
f (n + 1) = h(n, f (n)) y sinon
On a donc f RP car définie par schéma de récurrence a partir de fonctions elles mêmes RP (h est définie
par cas en fonction de P , donc RP).

Exercice 12.
Montrer que les fonctions calculant le plus petit commun multiple et le plus grand diviseur commun de deux
nombres sont récursives primitives.

2
Solution de l’exercice 12.

Soit m(x, y) = µk 6 xy div(x, k) et div(y, k) et (∀s 6 xy (div(x, s) et div(y, s) ⇒ div(k, s))) , où div(u, v) est
la fonction testant si u divise v. Alors m calcule le plus petit commun multiple de x et y, car elle cherche le plus
petit entier k qui soit divisible par x et y et tel que si un autre entier s est divisible par x et y alors k divise s.
L’expression symbolique donnée ci-dessus traduit cette phrase, en ajoutant des bornes pour le schéma µ et la
quantification.
De même, le plus grand diviseur commun pourrait s’obtenir par une expression similaire, en traduisant ses
propriétés, mais il peut aussi se calculer à partir du produit de x et y et de leur p.p.c.m..

Exercice 13. √ √
√ décimale de n : n = a0 , a1 a2 a3 · · · , où a0 est un
Soit n entier, on lui associe la suite (ai )i∈N de l’écriture
entier et chaque ai pour i > 1 est un chiffre de 0 à 9 (si √ n est un entier, ai vaut 0 pour i > 1). Montrer que la
fonction f qui à (n, i) associe ai (dans la suite associée à n) est récursive primitive.

Solution de l’exercice 13. √

Montrons que la fonction qui à n associe b nc est récursive primitive.
On cherche le plus petit entier k inférieur ou égal à x tel que (k + 1)2 soit supérieur strictement à x. Cette
fonction est récursive primitive par composition de fonctions récursives primitives et par minimisation bornée.
Deux solutions pour la suite :
√ √ √
1. On a vu que n 7→ b nc est récursive primitive.(Donc φ : (n, i) 7→ b10i nc = b 102i nc est récursive pri-
√
b nc si i = 0
mitive par composition. On pose alors f (n, i) = , qui est récursive primitive
φ(n, i) modulo 10 si i > 1
car définie par cas à partir de fonctions récursives primitives.
( √
b nc si i = 0
2. f (n, 0) = i
√ .
µk 6 9 (10 | b10 nc − k) si i > 1

Exercice 14.
Soit A l’ensemble des nombres entiers dont l’écriture en base 10 est un palindrome (par exemple 13266231 ou
754434457). Montrer que A est récursif primitif.

Solution de l’exercice 14. √

On a vu comment extraire un chiffre d’un nombre dans l’exercice concernant le développement décimal de n.
Soit donc c la fonction qui sur la donnée d’un entier n renvoie la valeur du ième chiffre de n (en partant de la
droite, donc le chiffre correspondant à la puissance i de 10) dans le développement de n en base 10. c(n, i) est
le reste modulo 10 de la division entière de n par 10i et est donc bien RP.
De même, il est facile de définir une fonction RP l qui renvoie la plus grande puissance de 10 apparaissant dans
n : l(n) = µk ≤ n (10k+1 > n).
Un entier n est alors un palindrome ssi ∀i ≤ b n2 c, c(n, i) = c(n, l(n) − i), ce qui nous donne bien un test RP.

Exercice 15.
Soit g une fonction récursive primitive. Soit f la fonction définie par : f (0, x) = g(x) et f (n+1, x) = f (n, f (n, x)).
Montrer que f est récursive primitive.

Solution de l’exercice 15.

n
Montrer par récurrence sur n que f (n, x) = g 2 (x).

Exercice 16.
Montrer qu’une fonction f est primitive récursive ssi le graphe de f est primitif récursif et f est majorée par
une fonction primitive récursive.

Solution de l’exercice 16.

Si f est récursive primitive elle est majorée par elle-même et la fonction caractéristique de son graphe est
χGf (x, y) = χ= (x, f (x)). Réciproquement, si on sait que f est majorée par g, alors on peut écrire f (x) = µy ≤
g(x). (x, y) ∈ Gf .

Exercice 17.
Soit S ∗ l’ensemble des suites finies d’entiers non vides et α : S ∗ → N la fonction qui à une suite non vide
(x1 , . . . , xp ) associe α(x1 , . . . , xp ) = α2 (p, αp (x1 , . . . , xp )).
1. Montrer que α est une injection dont l’image est un ensemble récursif primitif.

3
 2. Montrer que la fonction φ : N3 → N définie par :
(
βpi (x) si 1 6 i 6 p
φ(i, p, x) =
0 sinon

est récursive primitive.

3. En déduire qu’il existe une fonction récursive primitive γ ∈ F2 qui sur la donnée de deux entiers z et i
renvoie le i-ième élément de la suite finie d’entiers codée par z via α.

Solution de l’exercice 17.

Remarque : α n’est pas récursive primitive car ce n’est pas une fonction de Nk dans N pour un entier k fixé.

1. Montrons que α est injective. Soit (x1 , . . . , xm ) et (y1 , . . . , yn ) appartenant à S ∗ . Si α(x1 , . . . , xm ) =

α(y1 , . . . , yn ), alors α2 (m, αm (x1 , . . . , xm )) = α2 (n, αn (y1 , . . . , yn )). Ceci implique par injectivité de α2
que m = n et αm (x1 , . . . , xm ) = αm (y1 , . . . , ym ), donc m = n et xi = yi , ∀i ∈ {1, . . . , m}. α est bien
injective.
Montrons maintenant que l’image de α est un ensemble récursif primitif. Comme α2 est une bijection de N2
dans N, on doit déterminer l’ensemble A des couples de la forme (m, αm (x1 , . . . , xm )) pour (x1 , . . . , xm ) ∈
S ∗ . Tout couple de la forme (0, n) n’appartient pas à A.
Soit un couple (m, n) ∈ N∗ ×N. On sait que αm est une bijection de Nm dans N , donc il existe (x1 , . . . , xm )
tels que n = αm (x1 , . . . , xm ). Donc Im(α) = {n | β21 (n) 6= 0} Comme le test “β21 (n) 6= 0” est récursif
primitif, Im(α) est un ensemble récursif primitif.

2. Soit la fonction φ de N3 dans N définie par :

(
βpi (x) si 1 6 i 6 p,
φ(i, p, x) =
0 sinon.
On utilise le schéma de récurrence sur p pour donner une définition récursive primitive de φ.
 (
 x si i = 1,
φ(i, 1, x) =






 0 sinon.



 

 0 si i = 0 ou si i > p + 1,
 
φ(i, p, x) si i 6 p − 1,




 φ(i, p + 1, x) = 1
β2 (φ(p, p, x)) si i = p,

 

 
  2
 β2 (φ(p, p, x)) si i = p + 1.
Mais la définition ci-dessus ne correspond pas au schéma de récurrence vu en cours, car on a seulement
le droit d’utiliser la valeur “précédente” de la fonction qu’on est en train de calculer, à savoir ici φ(i, p, x).
Cela ne pose pas de problèmes pour le cas i = p de la troisième ligne, car alors φ(i, p, x) = φ(p, p, x),
mais il reste la dernière ligne et l’utilisation de φ(p, p, x) qui n’est pas la même chose que φ(i, p, x), car
on est dans le cas i = p + 1. On définit donc une fonction auxiliaire ψ pour calculer φ(p, p, x) = βpp (x).
On montre que cette fonction est récursive primitive par application d’un schéma de récurrence :
(
ψ(1, x) =x
p+1 .
ψ(p + 1, x) = βp+1 (x) = β22 (ψ(p, x))
Ceci nous permet de compléter la définition par schéma de récurrence de la la fonction φ et de montrer
ainsi qu’elle est bien récursive primitive.

3. On définit maintenant facilement la fonction γ qui est bien récursive primitive : γ(z, i) = φ(i, β21 (z), β22 (z)).

Exercice 18.
On rappelle que π est la fonction qui à n associe le (n + 1)-ième nombre Soit Ω0 : S ∗ → N la fonction
Qnpremier.1+x
0
qui à une suite non vide d’entiers (x0 , . . . , xn ) associe Ω (x0 , . . . , xn ) = i=0 π(i) i .
1. Montrer que Ω0 est une injection dont l’image est un ensemble récursif primitif.

4
 2. Montrer que l’on peut définir une fonction récursive primitive δ 0 : N2 → N telle que, si z est de la forme
Ω0 (x0 , . . . , xn ) et si 0 6 i 6 n, alors δ 0 (z, i) est égal à xi .

Solution de l’exercice 18. Qn−1

Soit Ω0 : S ∗ → N la fonction qui à une suite non vide d’entiers (x0 , . . . , xn−1 ) associe i=0 p(i)1+xi .
Qm−1 Qn−1
1. Montrons que Ω0 est injective : si Ω0 (x0 , . . . , xm−1 ) = Ω0 (y0 , . . . , yn−1 ), alors i=0 p(i)1+xi = i=0 p(i)1+yi .
D’après le caractère unique de la décomposition d’un entier en facteurs premiers, m = n et xi = yi pour
0 6 i 6 n.
Étudions l’image de Ω0 : n appartient à l’image de Ω0 si et seulement si n > 2 et il ne manque pas
un élément dans la suite croissante des facteurs premiers de la décomposition de n. Nous allons essayer
d’exprimer ceci de différentes manières, ce qui se traduira par différentes expressions primitives récursives.
Dans la suite, p désigne le plus grand nombre premier divisant
n, ce qui peut être calculé de manière
récursive primitive : p = n µk 6 n (P (n k) ∧ (n k)|n) .
1. Pour tout q premier inférieur ou égal à p, q divise n. Ceci s’exprime par ∀q 6 p, (P (q) ⇒ q|n), donc
par combinaisons booléennes et quantification bornée sur des fonctions récursives primitives.
2. p est égal au plus grand facteur premier de n “avant un trou” (i.e. tel que le nombre premier

suivant p
n’apparaisse pas dans n). On fait ce test en posant i = µk 6 n p(k + 1) ne divise pas n et en testant
l’égalité de p et p(i).
3. Pour tout nombre premier q divisant n, alors tout nombre premier r inférieur ou égal à q divise n. On
exprime ceci de manière récursive primitive : ∀q 6 n, (P (q) ∧ q|n) ⇒ (∀r 6 q, P (r) ⇒ r|n).
4. Si un nombre premier divise n, alors le nombre premier précédent (s’il existe) divise aussi n. On a ici
une expression récursive primitive très simple : ∀i 6 n, p(i)|n ⇒ p(i 1)|n.
Notons que dans tous les cas ci-dessus (et en général), il faut faire attention aux cas “limites”. Ici pour n
valant 0 ou 1 il peut y avoir des problèmes, qu’on résoudra via une définition par cas.

2. Soit la fonction δ 0 de N2 dans N : δ 0 (z, i) = µk 6 z, p(i)k+2 ne divise pas z (on peut décider que δ 0 vaut
0 si z n’appartient pas à l’image de Ω0 ). δ 0 est bien récursive primitive.

Exercice 19.

1. Rappeler la définition d’un codage des suites finies vu en cours (α, Ω ou Ω0 ).

2. Donner une définition récursive primitive de la fonction qui à un entier n associe le code de la suite de
diviseurs premiers de n dans l’ordre croissant.

Solution de l’exercice 19.

1. Codage α ou codage Ω ou Ω0 . Nous choisirons Ω0 .

2. On définit d’abordPla fonction R qui à deux entiers n et k associe le k + 1e diviseur premier de n :
t
R(n, k) = µt ≤ n. i=0 χA (n, t) = k + 1, où A est l’ensemble des couples (n, t) tels que
Qnt est un diviseur
premier de n, dont on sait qu’il est récursif primitif (cours, TD). On renvoie ensuite k=0 π(k)1+R(n,k) .

Exercice 20. Qn
On rappelle que le codage Ω0 est défini par Ω0 (x0 , . . . , xn ) = i=0 π(i)1+xi . Montrer que le tri dans l’ordre
croissant d’une suite, l’entrée et la sortie étant codées par la fonction Ω0 , est récursif primitif.
Solution de l’exercice 20.
Il existe plusieurs façons d’exprimer cette fonction de tri. Nous allons décrire une solution possible. Nous
commençons par remarquer qu’il existe une fonction récursive primitive λ qui, sur la donnée d’un entier
z = Ω0 (x0 , . . . , xn ), renvoie l’entier n (et une valeur quelconque si z n’est pas dans l’image de Ω0 ) : λ(z) =
µk ≤ z . (π(k + 1) ne divise pas z). Nous allons ensuite coder une permutation σ de {0, . . . , n} par l’entier
Ω0 (σ(0), . . . , σ(n)). Il est facile d’écrire une fonction P qui teste si un entier p code bien une permutation comme
ci-dessus : P (p) vaut 1 ssi ∀i ≤ λ(p), ∃j ≤ λ(p), δ 0 (p, j) = i. Nous considérons maintenant la fonction E(y, z, p)
qui teste si la permutation codée par p transforme la suite codée par y en la suite codée par z (et renvoie 0 si ce ne
sont pas des codes ou si les longueurs ne sont pas compatibles) : E renvoie 1 ssi ∀i ≤ λ(y), δ 0 (y, i) = δ 0 (z, δ 0 (p, i)).
Il nous faudra aussi la fonctoin T (y) qui vérifie si une liste est triée : ∀i ≤ λ(y), δ 0 (y, i − 1) ≤ δ 0 (y, i) Enfin, sur
2
l’entrée z, notre fonction de tri va renvoyer le plus petit entier y ≤ z (z+1) tel que y soit une liste triée et qu’il
0
existe un codede permutation p ≤ Ω (0, . . . , λ(z)) de sorte que E(y, z, p).

5
Exercice 21.
Soit f la fonction de N dans N définie par :

f (0) = 1, f (1) = 1, f (n + 2) = f (n + 1) + f (n).

Montrer que f est récursive primitive.

Solution de l’exercice 21.

Cette fonction est définie (mathématiquement) par récurrence, mais il ne s’agit pas d’une application du schéma
de récurrence, car on utilise les deux valeurs précédentes de la fonction. La définition donnée ne nous permet
donc pas de conclure que la fonction est récursive primitive. Pour cela, on définit une fonction intermédiaire F
par F (n) = α2 (f (n), f (n + 1)). Montrons par le schéma de récurrence que F est récursive primitive :

F (0)
 = α2 (f (0), f (1)) = α2 (1, 1),


F (n + 1) = α2 (f (n + 1), f (n + 2)) = α2 f (n + 1) , f (n + 1) + f (n)


= α2 β22 (F (n)) , β22 (F (n)) + β21 (F (n))


F est bien récursive primitive. Comme f = β21 ◦ F , f est récursive primitive par composition.

Exercice 22.
Montrer que l’ensemble des fonctions récursives primitives est clos par le schéma de récurrence sur la suite
des valeurs, c’est-à-dire que le calcul d’une fonction en n peut faire intervenir toutes les valeurs prises par la
fonction sur les valeurs plus petites que n.
Soit g : Np → N et h : Np+2 → N des fonctions récursives primitives, montrer que la fonction f : Np+1 → N
définie ci-dessous est récursive primitive :

f (a1 , . . . , ap , 0) = g(a1 , . . . , ap ),


f (a1 , . . . , ap , n + 1) = h a1 , . . . , ap , n, Ω0 f (a1 , . . . , ap , 0), . . . , f (a1 , . . . , ap , n) .

Solution de l’exercice 22.

On note ā pour a1 , . . . , ap afin d’alléger les notations. On considère la fonction F (ā, n) = Ω0 (f (ā, 0), . . . , f (ā, n)).
Montrons par un schéma de récurrence classique que F est récursive primitive sous les hypothèses de l’énoncé.
Commençons par donner le cas de base :

F (ā, 0) = Ω0 (f (ā, 0)) = 21+g(ā) .

Donnons maintenant l’étape de récurrence :

 
F (ā, n + 1) = Ω0 f (ā, 0), . . . , f (ā, n), f (ā, n + 1)
= Ω0 f (ā, 0), . . . , f (ā, n) · p(n + 1)f (ā,n+1)

= F (ā, n) · p(n + 1)h(ā,n,F (ā,n)) .

La dernière expression est bien récursive primitive et ne fait intervenir que F (ā, n), c’est-à-dire la valeur de la
fonction F pour le paramètre n. La fonction F est alors récursive primitive, ainsi que la fonction f obtenue par
f (ā, n) = δ 0 (F (ā, n), n).

Exercice 23.
Soit g1 , g2 , h des fonctions récursives primitives. Montrer que la fonction f définie par

f (0, y) = g1 (y), f (x + 1, 0) = g2 (x), f (x + 1, y + 1) = h(x, y, f (x, y + 1), f (x + 1, y))

est récursive primitive.

Solution de l’exercice 23.

On va calculer la fonction par diagonales (i.e., on calcule d’un coup toutes les valeurs f (x, y) pour x+y constant).

6
Posons donc F (n) = Ω0 (f (n, 0), . . . , f (0, n)). Montrons que la fonction F est récursive primitive par un schéma
de récurrence :
= Ω0 (f (0, 0)) = 21+g1 (0)


 F (0)
F (n + 1) = Ω0 (f (n + 1, 0), . . . , f (i, n + 1 i), . . . , f (0, n + 1))





= Ω0 (g2 (n), . . . , f (i, n + 1 i), . . . , g1 (n + 1))

Q

1+g2 (n) n h n i,i 1,f (n i,i),f (n+1 i,i 1)
= 2 · p(i) · p(n + 1)1+g1 (n+1)




 i=1


h n i,i 1,δ 0 (F (n),i),δ 0 (F (n),i 1)
 Qn
= 21+g2 (n) · · p(n + 1)1+g1 (n+1)

i=1 p(i)


La fonction f est donc elle aussi récursive primitive car f (x, y) = δ 0 (F (x + y), y).

Exercice 24.
Soit p un entier non nul. Montrer que l’ensemble ci-dessous est récursif primitif :
Ep = {(a0 , . . . , ap ) ∈ Np+1 | le polynôme a0 + a1 X + · · · + ap X p a un zéro dans Z}.

Solution de l’exercice 24.

Soit p un entier non nul et soit Ep l’ensemble des uplets (a0 , . . . , ap ) ∈ Np+1 tels que le polynôme a0 +a1 X +· · ·+
ap X p a une racine dans Z. Montrons que Ep est récursif primitif. On note Q le polynôme a0 + a1 X + · · · + ap X p .
Comme Q a des coefficients positifs ses racines ne peuvent être que négatives ou nulles.

Si a0 = 0, 0 est une racine entière de Q et l’uplet (a0 , . . . , ap ) appartient à Ep .

Comme nous pouvons faire le test sur a0 de manière récursive primitive, nous supposons maintenant que a0 6=0.
Dans ce cas, toute racine n est strictement négative et les parties positives et négatives dans l’évaluation du
polynôme doivent se compenser : a0 + a2 n2 + · · · + ap np = a1 (−n) + a3 (−n)3 + · · · + ap−1 (−n)p−1 . (On a supposé
ici que p est pair. Une petite modification sur les indices suffit pour écrire le cas où p est impair.)

Nous avons donc une caractérisation récursive primitive des racines, il nous reste à avoir une borne sur une
racine entière, pour pouvoir utiliser une quantification bornée. Or Q(n) = 0 implique que a0 = −n(a1 + a2 n +
· · · + ap np−1 ), donc que n divise a0 .

La fonction caractéristique de Ep (p pair) teste donc s’il existe un m inférieur ou égal à a0 tel que a0 + a2 m2 +
· · · + ap mp = a1 m + a3 m3 + · · · + ap−1 mp−1 ou si a0 = 0. Notre ensemble Ep est bien récursif primitif.

Exercice 25.

1. Montrer que les fonctions polynômes à plusieurs variables à coefficients dans N sont primitives récursives.

2. En s’inspirant du codage des suites finies dans N utilisant la décomposition en facteur premiers, proposer
un codage Θ de l’ensemble N[X] des polynômes à une variable à coefficients dans N qui soit bijectif. Plus
précisément, on veut :
(i) Θ : N[X] → N bijective ;
(ii) il existe une fonction primitive récursive c : N × N → N, telle que c(i, n) est le coefficient de degré i
dans le polynôme Pn = Θ−1 (n) ;
(iii) il existe une fonction primitive récursive d : N → N telle que d(n) est le degré du polynôme Pn =
Θ−1 (n) (on considère que le degré du polynôme nul est 0).
On note dorénavant Pn pour Θ−1 (n) (ou pour la fonction polynôme associée à Pn ).
3. Montrer que l’on peut coder la fonction qui applique une fonction polynôme à un entier, plus précisément,
montrer que la fonction a : N × N → N vérifiant a(n, x) = Pn (x) est primitive récursive.
4. Soit les deux fonctions p : N → N et i : N → N telles que Pp(n) , respectivement Pi(n) soit le polynôme dont
les monômes sont exactement les monômes de puissance paire, respectivement impaire, de Pn . Montrer
que p et i sont primitives récursives.
5. En déduire une fonction partielle récursive f : N → N telle que si Pn = Θ−1 (n) possède un zéro dans Z,
alors f (n) est la valeur absolue d’un zéro de Pn , sinon f n’est pas définie.
6. En fait on peut trouver une fonction primitive récursive qui calcule un zéro de Pn . Montrer qu’il existe
une fonction primitive récursive g : N → N, telle que si Pn possède un zéro dans Z, alors g(n) > 0 et
g(n) − 1 est la valeur absolue d’un zéro de Pn , sinon g(n) = 0.

7
 7. En déduire que l’ensemble des n tels que Pn possède un zéro dans Z est primitif récursif.

Solution de l’exercice 25.

On utilise la fonction π : N → N telle que π(n) soit le n + 1 nombre premier, dont on sait qu’elle est primitive
récursive.
1. Les fonctions polynômes s’obtiennent par composition à partir de l’addition, de la multiplication et des
fonctions de projections, et sont donc primitives récursives. (Faire éventuellement une démonstration par
récurrence sur le degré.)
2. On utilise la définition d’un polynôme comme une suite d’entiers à support fini, i.e. la suite est nulle
sauf pour un nombre fini d’indices. Soit P = (ci )i∈N un polynôme et d le plus petit indice tel que
Qd
∀j > d, cj = 0, alors posons Θ(P ) = i=0 π(i)ci − 1. L’existence de la décomposition en facteur premiers
d’un entier non nul nous assure que cette application est surjective, l’unicité à des exposants nuls près
nous assure de l’injectivité.
(i) Θ est bijective d’après ce qui précède.
(ii) Soit c : N × N → N, telle que

c(i, n) = µp 6 n (π(i)p+1 6 | (n + 1)).

On a bien défini ci-dessus c(i, n) le coefficient de degré i dans le polynôme Pn = Θ−1 (n) : le coefficient
est forcément plus petit que le code du polynôme car pour tous i et p, on a p < π(i)p , et comme
c(i, n) = p si et seulement si π(i)p | (n + 1), alors p < n + 1. La fonction c est primitive récur-
sive par minimisation bornée sur un prédicat primitif récursif (stabilité par combinaison booléenne ;
l’exponentielle, π et le prédicat | sont primitifs récursifs).
(iii) Soit d : N → N telle que



d(n) = n µp 6 n (π(n p) | (n + 1) .

On a bien défini d(n) comme le degré du polynôme Pn = Θ−1 (n), en effet ce degré est forcément
inférieur ou égal au code du polynôme car pour tout entier q, q < π(q), d(n) est donc le plus grand
nombre premier qui divise n + 1, pour n 6= 0, et d(0) = 0. On a bien que d est primitive récursive
(composition, minimisation bornée, l’exponentielle, π et le prédicat | sont primitifs récursifs).
3. soit a : N × N → N vérifiant
d(n)
X
a(n, x) = c(i, n).xi .
i=0

On a bien a(n, x) = Pn (x) , et an est primitive récursive, d’après les questions P

précédentes et par somme
n
bornée (remarque : on n’a pas vraiment besoin de d, car on a aussi a(n, x) = i=1 c(i, n).xn .).
4. On sait que «être pair» est un prédicat primitif récursif, soit χ sa fonction caractéristique. On définit
p : N → N et i : N → N par :
d(n) d(n)
Y Y
χ(i).c(i,n)
p(n) = π(i) 1 i(n) = π(i)(1 χ(i)).c(i,n) 1.
i=0 i=0

On a bien que Pp(n) , respectivement Pi(n) est le polynôme dont les monômes sont exactement les monômes
de puissance paire, respectivement impaire, de Pn . On a aussi p et i sont primitives récursives : produit
borné et question ??.
5. Un zéro d’un polynôme à coefficients dans N est forcément négatif. Si f (n) est la valeur absolue d’un
zéro de Pn , alors −f (n) est un zéro de Pn , or, pour x ∈ N, Pn (−x) = 0 s’écrit aussi Pp(n) (x) = Pi(n) (x).
Si l’on définit f : N → N par

f (n) = µx (Pp(n) (x) = Pi(n) (x)) = µx (a(p(n), x) = a(i(n), x)).

on a donc bien que −f (n) est un zéro de Pn . Par ailleurs f est partielle récursive par minimisation sur
un prédicat qui est récursif d’après les questions ?? et ??.
6. On peut facilement borner la minimisation ci-dessus en remarquant qu’un zéro entier d’un polynôme à
coefficients entiers est un diviseur de son coefficient de degré nul, et donc, si dernier est non nul, est
toujours inférieur ou égal à ce coefficient. Si le coefficient de degré nul est 0, on choisit 0 comme zéro du

8
 polynôme. Pour pouvoir distinguer les polynômes qui n’ont pas de zéro de ceux qui s’annulent en zéro,
on peut translater de 1 le zéro cherché, on définit g : N → N,
 
g(n) = µx 6 c(0, n) x > 1 et a(p(n), x 1) = a(i(n), x 1) .

On a bien que si Pn possède un zéro dans Z, alors g(n) > 0 et g(n) − 1 est la valeur absolue d’un zéro
de Pn , sinon g(n) = 0. On a aussi que g est primitive récursive par minimisation bornée sur un prédicat
primitif récursif d’après les questions ?? et ??.
7. L’ensemble des n tels que Pn possède un zéro dans Z a pour fonction caractéristique sgn ◦ g, où sgn est
la fonction qui vaut 1 ssi son argument est non nul. Cet ensemble est donc primitif récursif.

Exercice 26.
On définit les fonctions élémentaires F E comme le plus petit sous-ensemble de F ∗ contenant :
— les fonctions nulles 0p ;
— la fonction successeur ;
— la relation d’égalité R= (définie par R= (x, y) = 1 si x = y et R= (x, y) = 0 sinon) ;
— les projections ;
et clos par les opérations suivantes :
— composition ;
— somme bornée et produit borné. Cela signifie que si cet ensemble contient la fonction

(y, x1 , . . . , xn ) 7→ f (y, x1 , . . . , xn ),

alors il contient aussi les fonctions

X Y
(z, x1 , . . . , xn ) 7→ f (y, x1 , . . . , xn ) et (z, x1 , . . . , xn ) 7→ f (y, x1 , . . . , xn ).
y<z y<z

1. Montrer que F E est un sous-ensemble des fonctions récursives primitives.

2. a) Montrer que la fonction (x, y) 7→ xy est élémentaire.
b) Montrer que la relation R6 est élémentaire (la relation R6 est définie par R6 (x, y) = 1 si x 6 y et
R6 (x, y) = 0 sinon).
c) Montrer que la soustraction propre est élémentaire (on rappelle que x y = x − y si x > y et
x y = 0 sinon).
d) Montrer que (x, y) 7→ x + y est élémentaire. Indication : exprimer la somme à l’aide des produits
(x + 1)(y + 1) et xy, et de la soustraction propre.

On définit les fonctions er : N → N par e0 (x) = x et er+1 (x) = 2er (x) .

x
3. Montrer que pour tout x ∈ N, x2 < 22 = e2 (x).

Dans cet exercice, on dit qu’une fonction f (x1 , . . . , xp ) est dominée par er si pour tout x1 , . . . , xp ∈ N,
f (x1 , . . . , xp ) 6 er (max(x1 , . . . , xp )).

4. Montrer que pour toute fonction élémentaire (x1 , . . . , xp ) 7→ f (x1 , . . . , xp ), il existe un entier r tel que er
domine f .
5. Montrer que la fonction n 7→ en (n) est récursive primitive.
6. En déduire que F E est un sous-ensemble strict des fonctions récursives primitives.

Solution de l’exercice 26.

1. On sait les fonctions listées sont récursives primitives et l’ensemble des fonctions récursifs primitifs est
clos par composition et somme et produit bornés, donc F E est un sous-ensemble des fonctions récursives
primitives.
2. a) xy = z<y p12 (x, y). P
P
b) R≤ (x, y)P= R= (x, y) + z<y R= (z, x).
c) x y = z<y R≤ (x, z).
d) x + y = (x + 1)(y + 1) xy 1.

9
 x
3. x < 2x , donc x2 < 22x ≤ 22 .
4. Nous allons montrer cette propriété par induction. Elle est vraie pour les fonctions élémentaires “de base”.
Vérifions alors qu’elle est stable par composition. Soit f : Nn → N et g1 , . . . , gn : Np → N des fonctions
élémentaires. Alors par hypothèse d’induction il existe r, r1 , . . . , rn tels que er domine f et eri domine gi .
Soit x1 , . . . , xp ∈ N, alors gi (x1 , . . . , xp ) ≤ eri (max(x1 , . . . , xp )). On a alors f (g1 , . . . , gn )(x1 , . . . , xp ) ≤
er (max(g1 (x̄), . . . , gn (x̄))) ≤ er (es (max(x1 , . . . , xp ))), où s est le maximum des ri . On voit donc que
f (g1 , . . . , gn ) est dominée par er+s .
Vérifions qu’elle P est stable parP somme bornée. Soit f une fonction élémentaire, donc dominée par un cer-
tain er . Alors y<z f (y, x̄) ≤ y<z er (max(y, x1 , . . . , xn )) ≤ z·er (max(z, x1 , . . . , xn )) ≤ (er (max(z, x1 , . . . , xn )))2 ≤
er+2 (max(z, x1 , . . . , xn )).
Vérifions Q qu’elle est stableQpar produit borné. Soit f une fonction élémentaire, donc dominée par un certain
er . Alors y<z f (y, x̄) ≤ y<z er (max(y, x1 , . . . , xn )) ≤ (er (max(z, x1 , . . . , xn )))z ≤ 2z·(er−1 (max(z,x1 ,...,xn ))) ≤
2
2(er−1 (max(z,x1 ,...,xn ))) ≤ er+2 (max(z, x1 , . . . , xn )).
5. Il est facile de voir que e : (n, x) 7→ en (x) est récursive primitive, par schéma de récurrence sur n, puis
on en déduit que n 7→ en (n) l’est aussi.
6. n 7→ en (n) ne peut pas être dominée par une fonction er , car si elle l’était on aurait er+1 (r+1) ≤ er (r+1).
Donc n 7→ en (n), qui est récursive primitive, n’est pas élémentaire.

10