[PDF] [PDF] Fonctions récursives FONCTIONS R´ECURSIVES Exercice 175

View - Download [PDF] Fonctions récursives

Previous PDF

Next PDF

Chapitre7

Fonctionsr´ecursives

L'objectifdecettepartieest d'abordd evoirunautremod`e ledecalculque lesmachine sdeTuringetdemontrerq u'ilal emˆemepouvoirexpres sifque les machinesdeTuring(doncd 'apporte runt´emoin`alath`e sedeChurch) .L'autre objectifestdemontrerle sth´eor`em esd'in compl´etudesdus`aG ¨odel.

7.1Fonctions r´ecursivesprimitive s

fd´esigneraunefonctiondeN k dansN.Les fonction stotalessontaussides applications.f(n 1 ,...,n k )=?sifn'estpasd´efiniee nn 1 ,...,n k

Lesfonctionsinitialessont

- lesprojec tionsP i k :N k 7!N.P i k (n 1 ,...,n k )=n i - lesuccesseur S(n)=n+1 - lafonct ionnulleZ(n)=0 - lafonct ionconstante0(`a0argum ents). Unen sembled'applicationsFestferm´eparcomposi tionsi,pourtout es fonction⇠:N k 7!Net 1 m :N n

7!N,la foncti on:N

n

7!Nd´efinie

par(~n)=⇠( 1 (~n),..., m (~n))estd ansF.On noteComp m 1 n )la fonctionainsiobtenue. Unen sembled'applicationsFestferm´eparr´ecursio nprimiti vesi,pour toutesfonctions⇠, 2F,la foncti ond´efinieparr´ecurrence par: (m,~n)= ⇠(~n)sim=0 ((m1,~n),m1,~n)sim>0 estdansF.On notePrim(⇠, )la foncti onainsiobtenue. Definition7.1.1L'ensembledesfonctionsr´ecursivespr imitivesestlepl uspe- titensemble contenantlaconst ante0,lesfonctionsinitial es,clos parcomposi- tionetr´ecursi onp rimitive. Touteslesfonctions r´ecursi vesprimitivess'obtien nentainsi`apartirdefonc- tionsdebaseetd esop´er ationsPrimetComp n Exemple7.1.1f(n,m)=n+mestprimitiv er´ecursive:f=Prim(P 1 1 ,Comp 1 (S,P 1 3 2 (+,P 1 3 ,P 3 3 165

166CHAPITRE7.FONCTIONSR

ECURSIVES

Exercice175

Montrerquelesfonction ssuivante ssontr´ecu rsivesprimitives(les pr´edicatssont vuscommede sfonctions`av aleurdans{0,1},le sfonctionsB ool´eennestraitent lesentie rsnonnulscomme1).

1.lafactor ielle

2.letest d'´egalit´e

3.Lesconne cteurslogiques^,_,¬.

Exercice176

Festclosparmax imisation born´eesi,pourtout esfonctions ⇠, 2Ftellesque

8~n,9m (~n).⇠(~n,m )=0

lafonct iond´efiniepar: (~n)=m ax m (~n) (⇠(~n,m )=0) estdansF. Montrerquel'ensembl edesfonct ionsr´ecursivesprimitivesestfe rm´epar maximisationborn´ee.

Exercice177

Montrerque,commedans l'exercicep r´ec´edent,l 'ensembl edesfonctionsr´ecursives primitivesestclosparminimisationb orn´ee.

Exercice178(4)

Montrerquelafonctionq ui,`aune ntiernassocielepluspetitn ombrep remier plusgrandquenestr´ ecursiveprimitive.

Exercice179

Montrerqu'ilexisteu nefonctionJ:N

2 !N,et deuxfon ctionsK,L:N!N tellesque:

1.J,K,Lsontr´ecur sivesprimitives

2.Jestunebij ection

3.pourtousx,y,K(J(x,y))=xetL(J(x,y))=y.

L'exercicesuivantmontreunecarac t´erisationimportantd esfonctionsr´ecur sives primitives:cesontlesfonctionsque l'on peutd´ efinirexc lusivemen tavecdes bouclesfor.C' estaussicequedit l'exercices urmami nimisation born´ee,d' une autrefa¸con.

Exercice180(5)

Sihestunefonc tiondeNdansNonapp elleit´erationdehlafonct ionf(n,x) d´efiniepar: f(n,x)= xsin=0 h(f(n1,x))sinon Montrerquelapluspet iteclasse defonct ionssurlesent iersquicontientles fonctionsdebase,lesfonct ionsJ,K,Letquie stclosepari t´eratione tcompo- sition,co¨ıncideav ecl'ensembledesfonctionsr´ec ursivesprimi tives.

7.1.FONCT IONSR

ECURSIVESPRIMITIVES167

Exercice181(5)

Montrerquelafonction suivante,d ´efini eparr´ecurrence,est r´ecursiveprimitive. 8 f(0)=1 f(1)=1 f(n+2)= f(n+1)+ f(n)Sin2N

Hi´erarchiedeGrzegorczyk

Ond´efi nitparr´ecurrencesurnlasuit edefonctionsprim itives r´ecursives commesuit: 0 (m)=m+1 n+1 (0)= n (1) n+1 (m+1)= n n+1 (m))

Onmontr e,parr´ecurrencesu rnque:

Lemme7.1.1Pourtoutn,

n estunef onctionr´ ecursiveprimitive. Parr´ec urrencesurm,onm ontr esuccessivemen tlesr´esultatssuivantspour lespremi` eresfonctionsdelahi´erarchie: 1 (m)=m+2 2 (m)=2m+3 3 (m)=2 m+3 3 4 (m)= m+3 2 2 2 3

Lemme7.1.21.Pourtousn,m,

n (m)1+m

2.Lesfonct ions

k sontstrictement croissantespourtoutk

3.Pourtousn,m,k,

n (m)+k n+k (m)

Preuve:

1.Parr´ec urrencesur(n,m)(or donn´eslexicographiquement) :

0 (m)= m+1,cequ imontre lapropri´ et´edanslecasdebas e. n+1 (0)= n (1) n+11par hypoth` eseder´ecurrence. n+1 (m+1)= n n+1 (m)) n+1 (m)+1 parh ypot h`esed er´ecurrence.Et n+1 (m)m+1( par

H.R.)donc

n+1 (m+1)m+2.

2.Parr´ec urrencesurkonmon treque,pourtoutm,

k (m+1)> k (m):si k=0on abi enm+2>m+1. k+1 (m+1)= k k+1 (m)) k+1 (m)+1 parlepr emierp ointdulemme.Donc k+1 (m+1)> k+1 (m).

3.Onmontr e,parr´ecurrencesu r(n,m),que

n+1 (m) n (m)+1. Si n=0, n+1 (m)=m+2 0 (m)+1. n+2 (0)= n+1 (1) n (1)+1 (parhypoth `eseder´ecurrence).Or n (1)= n+1 (0).Donc n+2 (0) n+1 (0)+1.

168CHAPITRE7.FONCTIONSR

ECURSIVES

n+2 (m+1)= n+1 n+2 (m)) n+1 n+1 (m)+1)(parhyp oth`esede r´ecurrenceetparcroissancede n+1 n+1 n+1 (m)+1) n n+1 (m)+

1)+1(parhyp oth`eseder ´ecurrence),et

n n+1 (m)+1)+1 n n+1 (m))+ 1= n+1 (m+1)+ 1.

Lemme7.1.3Pourtous k,m,n,

k m (n))

2+max(k,m)

(n).

Preuve:

Onuti liselesr´esultatsdel' exercice7. 1.2sansmention.SoitM=max (k,m). k m (n)) M M+1 (n)) M+1 (n+1) M+1 1 (n1))Sin>0 M+1 M+2 (n1)) M+2 (n) et,sin=0, M+1 (n+1) M+2 (0)etona encorel 'in ´e galit´e. Proposition7.1.1Pourtoutefo nctionr´ecursivepri mitive`aunargument⇠, ilexist eunefonctiondel ahi´erarchi edeGrzegorczyk n telleque

8m.⇠(m)

n (m)

Preuve:

Onprouv eparr´ecurrence surlen ombred'op´erationsutilis´eesdanslacon struc- tiondesfonc tionsprimi tivesr´ecursivesque, siestprimit iver´ecursive,alorsil existeunk telque(~n) k (max~n). - C'estvraipourlesf onctionsin itiales:P i k (~n) 0 (max~n),S(n) 0 (n),

Z(n)

0 (n). - Siestobtenue parcompositionde⇠, 1 m ,il su tde choisir k =2+ max( k ,k 1 ,...,k n enutil isantl'exercice7.1.2. - Siestobtenue parr´ecursionprimit ive: (m,~n)= ⇠(~n)Sim=0 ((m1,~n),m1,~n)Sim>0

Onmontr eparr´ecurrence surmque(m,~n)

m k k (max(~n)))Si m=0,al ors(0,~n)=⇠(~n) k (max(~n))parhy poth`es eder´ecurrence.

Sim>0,par hypoth` eseder´ecurrence,

(m1,~n) m1 k k (max(~n))).

Parcrois sancede

k etcomme m k (n)n+m,ona auss i (m,~n) k (max( m1 k k (max(~n))),m1,~n)) k m1 k k (max(~n))))

7.1.FONCT IONSR

ECURSIVESPRIMITIVES169

Paraille urs,

m k (n) k+1 (n+m)(p arr´ecurre ncesurm),donc (m,~n) 1+k (m+ k (max(~n))) Ilsu td' utiliseralorsler´esultatsurlacomp osition. Lafonctiond'Ackermannestlafonct ion`ade uxargumentsA(n,m)= n (m). Th´eor`eme7.1.1Lafonct iond'Ackermannn'estpasr´ ecursiveprimitive.

Preuve:

Sicett efonction´etaitr´ ecursiveprimitive ,d'apr`eslaproposi tion7.1.1,ilexis- teraitunentierktelque,pou rtoutn,A(n,n) k (n).Maise nchoisissan t n=k+1,on obti ent k+1 (k+1) k (k+1), cequic ontredi tler´esu ltatde l'exercice7.1.2.quotesdbs_dbs16.pdfusesText_22

[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