[PDF] TD 1 – Fonctions récursives primitives

View - Download TD 1 – Fonctions récursives primitives

Previous PDF

Next PDF

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 toutn2Nl"ensemblefngest récursif primitif. En déduire que tout sous-ensemble deNqui

est fini ou qui est le complémentaire d"un sous-ensemble fini deNest 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éfdéfinie parf(x;y) = 1six=yet0sinon est récursive primitive. Si on notecnla fonction

constante égale ànà une variable, on afng=f(11;cn)ce qui montre quefngest bien un ensemble récursif

primitif.

L"ensemble des ensembles récursifs primitifs étant clos par opérations booléennes, un sous ensemble fini deN

est la réunion de singletons deNqui sont récursifs primitifs et donc est récursif primitif. De même les ensembles

cofinis deNsont 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éristiquefdes nombres pairs se définit de la manière suivante par récurrence :f(0) = 1et

f(n+ 1) = 1f(n); elle est donc bien récursive primitive.

Exercice 3.

Soitpun entier non nul. Montrer que la fonction supp:Np!Nqui à(x1;:::;xp)associe le maximum de x

1;:::;xpest récursive primitive.

Solution de l"exercice 3.

Soitpun entier non nul , on veut montrer que la fonctionsuppqui aup-uplet(x1;:::;xp)associe le plus grand

desxipouriappartenant àf1;:::;pg. On fait une démonstration par récurrence surp. sup

1(x1) =x1;sup1=11(c"est la projection à un argument)

On suppose que les sup

ipouriappartenant àf1;:::;p1g, sont récursives primitives on regarde pour supp+1: sup p+1(x1;:::;xp+1) =sup2(supp(x1;:::;xp);xp+1) où sup

2(x;y) =x si x>yetysinon. Ainsi, supp+1est récursive primitive.

Donc la fonction sup

pest récursive primitive pour toutp2N.

Exercice 4.

Montrer que les fonctionsquotientetrestesont récursives primitives (par définition, on posex=y= 0siy= 0).

En déduire quef(x;y)jydivisexgest récursif primitif.

Solution de l"exercice 4.

Notonsqla fonction quotient. On aq(x;y) =k6x :(k+1)y > x, doncqest récursive primitive. La fonction

reste est égale àr(x;y) =xyq(x;y)l"est également.

Exercice 5.

Montrer que l"ensemble des nombre premiers est récursif primitif. En déduire que la fonctionqui ànfait

correspondre le(n+ 1)-ième nombre premier est récursive primitive.

Solution de l"exercice 5.

Un entiernest premier ssin >1et pour touta2 f2;n1g,ane divise pasn(qui peut s"écrire : pour tout

a < n,a <2ouane divise pasn). Ceci montre que l"ensemble des nombre premiers est récursif primitif.

La fonctionfqui ànfait correspondre le(n+ 1)-ième nombre premier est définie par récurrence :f(0) = 2et

f(n+ 1) =a6(f(n)! + 1):(a > f(n) etapremier). 1

Exercice 6.

Soitf:N!Nune fonction récursive primitive. Montrer que la fonctiongdéfinie parg(x) =ff:::f|{z} x+1fois(0) est récursive primitive.

Solution de l"exercice 6.

On définitgpar schéma de récurrence :(

g(0) =f(0) g(x+ 1) =f(g(x)).

Exercice 7.

Montrer que la fonctionx7!xx:::x

, où le nombre dexdans la tour d"exponentielles estx+ 1, est récursive primitive.

Solution de l"exercice 7.

On définit d"abord par schéma de récurrence une fonction récursive primitiveF(x;n) =xx:::x

, où le nombre de xdans la tour d"exponentielles estn:(

F(x;0) = 1

F(x;n+ 1) =xF(x;n). La fonction cherchée estF(x;x), qui est donc récursive primitive.

Exercice 8.

SoitEl"ensemble des entiers naturels qui sont la somme de deux carrés. Montrer queEest récursif primitif.

Solution de l"exercice 8.

x2Es"exprime par9s;t6x(s2+t2=x).

Exercice 9.

Soitf:N!Ndéfinie parf(a;b) =2(c;d)oùc=dest l"écriture simplifiée de la fractiona=bsib6= 0, et

c=d= 0sinon. Montrer que la fonctionfest récursive primitive.

Solution de l"exercice 9.

Il existe plusieurs solutions. On peut par exemple définirf(a;b)comme le plus petit entierk2(a;b)tel que

12(k)b=22(k)aetk6= 0.

Exercice 10.

Soitula fonction qui àn2Nassocie le(n+1)-ième entier naturel (dans l"ordre croissant) qui est une somme

de deux carrés. Montrer queuest récursive primitive.

Solution de l"exercice 10.

On définit la fonctionupar un schéma de récurrence :( u(0) = 0 u(n+ 1) =k6(u(n) + 1)2:k > u(n)et9x;y6k(x2+y2=k)

Exercice 11.

Soitfla fonction qui ànassocie le nombre d"entiers premiers inférieurs ou égaux àn. Montrer quefest

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) = 1sikest premier et0sinon. Ce

test est récursif primitif. On a alorsf(n) =Pn k=0P(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)), avech(n;y) =( y+ 1siP(n+ 1) = 1 ysinon.

On a doncfRP car définie par schéma de récurrence a partir de fonctions elles mêmes RP (hest définie

par cas en fonction deP, 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.

Soitm(x;y) =k6xydiv(x;k)et div(y;k)et(8s6xy(div(x;s)et div(y;s))div(k;s))), où div(u;v)est

la fonction testant siudivisev. Alorsmcalcule le plus petit commun multiple dexety, car elle cherche le plus

petit entierkqui soit divisible parxetyet tel que si un autre entiersest divisible parxetyalorskdivises.

L"expression symbolique donnée ci-dessus traduit cette phrase, en ajoutant des bornes pour le schémaet 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 dexetyet de leur p.p.c.m..

Exercice 13.

Soitnentier, on lui associe la suite(ai)i2Nde l"écriture décimale depn:pn=a0;a1a2a3, oùa0est un

entier et chaqueaipouri>1est un chiffre de0à9(sipnest un entier,aivaut0pouri>1). Montrer que la fonctionfqui à(n;i)associeai(dans la suite associée àpn) est récursive primitive.

Solution de l"exercice 13.

Montrons que la fonction qui ànassociebpncest récursive primitive.

On cherche le plus petit entierkinférieur ou égal àxtel que(k+ 1)2soit 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 quen7! bpncest récursive primitive. Donc: (n;i)7! b10ipnc=bp10

2incest récursive pri-

mitive par composition. On pose alorsf(n;i) =( bpncsii= 0 (n;i)modulo10sii>1, qui est récursive primitive car définie par cas à partir de fonctions récursives primitives.

2.f(n;0) =(

bpncsii= 0 k69 (10j b10ipnc k)sii>1.

Exercice 14.

SoitAl"ensemble des nombres entiers dont l"écriture en base 10 est un palindrome (par exemple13266231ou

754434457). Montrer queAest 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 depn.

Soit donccla fonction qui sur la donnée d"un entiernrenvoie la valeur duième chiffre den(en partant de la

droite, donc le chiffre correspondant à la puissanceide 10) dans le développement denen base10.c(n;i)est

le reste modulo10de la division entière denpar10iet est donc bien RP.

De même, il est facile de définir une fonction RPlqui renvoie la plus grande puissance de10apparaissant dans

n:l(n) =kn(10k+1> n).

Un entiernest alors un palindrome ssi8i bn2

c,c(n;i) =c(n;l(n)i), ce qui nous donne bien un test RP.

Exercice 15.

Soitgune fonction récursive primitive. Soitfla fonction définie par :f(0;x) =g(x)etf(n+1;x) =f(n;f(n;x)).

Montrer quefest récursive primitive.

Solution de l"exercice 15.

Montrer par récurrence surnquef(n;x) =g2n(x).

Exercice 16.

Montrer qu"une fonctionfest primitive récursive ssi le graphe defest primitif récursif etfest majorée par

une fonction primitive récursive.

Solution de l"exercice 16.

Sifest 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 quefest majorée parg, alors on peut écriref(x) =y

g(x):(x;y)2Gf.

Exercice 17.

SoitSl"ensemble des suites finies d"entiers non vides et:S!Nla fonction qui à une suite non vide (x1;:::;xp)associe(x1;:::;xp) =2(p;p(x1;:::;xp)).

1. Montrer queest une injection dont l"image est un ensemble récursif primitif.

3

2. Montrer que la fonction:N3!Ndéfinie par :

(i;p;x) =( ip(x)si16i6p

0sinon

est récursive primitive.

3. En déduire qu"il existe une fonction récursive primitive

2 F2qui sur la donnée de deux entierszeti

renvoie lei-ième élément de la suite finie d"entiers codée parzvia.

Solution de l"exercice 17.

Remarque :n"est pas récursive primitive car ce n"est pas une fonction deNkdansNpour un entierkfixé.

1. Montrons queest injective. Soit(x1;:::;xm)et(y1;:::;yn)appartenant àS. Si(x1;:::;xm) =

(y1;:::;yn), alors2(m;m(x1;:::;xm)) =2(n;n(y1;:::;yn)). Ceci implique par injectivité de2 quem=netm(x1;:::;xm) =m(y1;:::;ym), doncm=netxi=yi,8i2 f1;:::;mg.est bien injective. Montrons maintenant que l"image deest un ensemble récursif primitif. Comme2est une bijection deN2 dansN, on doit déterminer l"ensembleAdes couples de la forme(m;m(x1;:::;xm))pour(x1;:::;xm)2 S . Tout couple de la forme(0;n)n"appartient pas à A. Soit un couple(m;n)2NN. On sait quemest une bijection deNmdansN, donc il existe(x1;:::;xm) tels quen=m(x1;:::;xm). Donc Im() =fnj12(n)6= 0gComme le test "12(n)6= 0" est récursif primitif, Im()est un ensemble récursif primitif.

2. Soit la fonctiondeN3dansNdéfinie par :

(i;p;x) =( ip(x)si16i6p;

0sinon:

On utilise le schéma de récurrence surppour donner une définition récursive primitive de.

8>>>>>>>>>>><

>>>>>>>>>>:(i;1;x) =( xsii= 1;

0sinon:

(i;p+ 1;x) =8 >>:0sii= 0ou sii > p+ 1; (i;p;x)sii6p1;

12((p;p;x))sii=p;

22((p;p;x))sii=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 casi=pde 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 casi=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;x) =p+1 p+1(x) =22( (p;x)):

Ceci nous permet de compléter la définition par schéma de récurrence de la la fonctionet 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;12(z);22(z)).

Exercice 18.

On rappelle queest la fonction qui ànassocie le(n+ 1)-ième nombre premier. Soit

0:S!Nla fonction

qui à une suite non vide d"entiers(x0;:::;xn)associe

0(x0;:::;xn) =Qn

i=0(i)1+xi.

1. Montrer que

0est une injection dont l"image est un ensemble récursif primitif.

4

2. Montrer que l"on peut définir une fonction récursive primitive0:N2!Ntelle que, sizest de la forme

0(x0;:::;xn)et si06i6n, alors0(z;i)est égal àxi.

Solution de l"exercice 18.

Soit

0:S!Nla fonction qui à une suite non vide d"entiers(x0;:::;xn1)associeQn1

i=0p(i)1+xi.

1. Montrons que

0est injective : si

0(x0;:::;xm1) =

0(y0;:::;yn1), alorsQm1

i=0p(i)1+xi=Qn1 i=0p(i)1+yi.

D"après le caractère unique de la décomposition d"un entier en facteurs premiers,m=netxi=yipour

06i6n.

Étudions l"image de

0:nappartient à l"image de

0si et seulement sin>2et il ne manque pas

un élément dans la suite croissante des facteurs premiers de la décomposition den. 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,pdésigne le plus grand nombre premier divisantn, ce qui peut être calculé de manière

récursive primitive :p=nk6n(P(nk)^(nk)jn).

1. Pour toutqpremier inférieur ou égal àp,qdivisen. Ceci s"exprime par8q6p;(P(q))qjn), donc

par combinaisons booléennes et quantification bornée sur des fonctions récursives primitives.

2.pest égal au plus grand facteur premier den"avant un trou" (i.e. tel que le nombre premier suivantp

quotesdbs_dbs5.pdfusesText_10

[PDF] théorème de godel démonstration

[PDF] codage de godel

[PDF] théorème de gödel pdf

[PDF] arithmétique de robinson

[PDF] nombre de godel

[PDF] godel dieu

[PDF] théorème d'incomplétude pour les nuls

[PDF] incomplétude définition

[PDF] introduction ? la calculabilité pdf

[PDF] indemnité prof principal 2017

[PDF] isoe prof principal

[PDF] hsa prof

[PDF] indemnite tuteur stagiaire education nationale

[PDF] prime prof principal contractuel

[PDF] evaluation anglais 6ème description physique