Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Université Paris Diderot Année 2016–2017 UFR de mathématiques Logique et comple

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 ﬁni ou qui est le complémentaire d’un sous-ensemble ﬁni 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éﬁnie 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(π1 1, 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 ﬁni 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 coﬁnis 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éﬁnit 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 = π1 1 (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éﬁnition, 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 ⩽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éﬁnie par récurrence : f(0) = 2 et f(n + 1) = µa ⩽(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éﬁnie par g(x) = f ◦f ◦. . . ◦f | {z } x+1 fois (0) est récursive primitive. Solution de l’exercice 6. On déﬁnit g par schéma de récurrence : ( g(0) = f(0) g(x + 1) = f(g(x)) . Exercice 7. Montrer que la fonction x 7→xx...x , où le nombre de x dans la tour d’exponentielles est x + 1, est récursive primitive. Solution de l’exercice 7. On déﬁnit d’abord par schéma de récurrence une fonction récursive primitive F(x, n) = xx...x , où le nombre de x dans la tour d’exponentielles est n : ( F(x, 0) = 1 F(x, n + 1) = xF (x,n) . La fonction cherchée est F(x, x), qui est donc 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 ⩽x (s2 + t2 = x). Exercice 9. Soit f : N →N déﬁnie par f(a, b) = α2(c, d) où c/d est l’écriture simpliﬁée de la fraction a/b si b ̸= 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éﬁnir f(a, b) comme le plus petit entier k ≤α2(a, b) tel que β1 2(k) · b = β2 2(k) · a et k ̸= 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. On déﬁnit la fonction u par un schéma de récurrence : ( u(0) = 0 u(n + 1) = µk ⩽(u(n) + 1)2 . k > u(n) et ∃x, y ⩽k (x2 + y2 = 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 précédent : P(k) = 1 si k est premier et 0 sinon. Ce test est récursif primitif. On a alors f(n) = Pn k=0 P(k) qui est récursive primitive comme somme bornée de fonctions récursives primitives. 2. Par schéma de récurrence on pose : ( f(0) = 0 f(n + 1) = h(n, f(n)), avec h(n, y) = ( y + 1 si P(n + 1) = 1 y sinon . On a donc f RP car déﬁnie par schéma de récurrence a partir de fonctions elles mêmes RP (h est déﬁnie 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 ⩽xy div(x, k) et div(y, k) et (∀s ⩽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 quantiﬁcation. 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. Soit n entier, on lui associe la suite (ai)i∈N de l’écriture décimale de √n : √n = a0, a1a2a3 · · · , où a0 est un entier et chaque ai pour i ⩾1 est un chiﬀre 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 ⌊√n⌋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→⌊√n⌋est récursive primitive. Donc φ : (n, i) 7→⌊10i√n⌋= ⌊ √ 102in⌋est récursive pri- mitive par composition. On pose alors f(n, i) = ( ⌊√n⌋ si i = 0 φ(n, i) modulo 10 si i ⩾1, qui est récursive primitive car déﬁnie par cas à partir de fonctions récursives primitives. 2. f(n, 0) = ( ⌊√n⌋ si i = 0 µk ⩽9 (10 | ⌊10i√n⌋−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 chiﬀre 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 chiﬀre de n (en partant de la droite, donc le chiﬀre correspondant à la puissance uploads/s3/ td-1-corrige 1 .pdf