[PDF] [PDF] Calculabilité - IRIF Ce document contient les notes

View - Download [PDF] Calculabilité - IRIF

Previous PDF

Next PDF

Calculabilit´e

Support de cours et de TD

Eugene Asarin

Grenoble - 2003

Table des mati`eres

0.1 Quelques exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

0.2 Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 5

0.2.1 Exercices - sans th´eorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

0.3 Calculabilit´e vs Complexit´e . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 6

1 Mod`eles de calcul7

1.1 Fonctions r´ecursives primitives . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 7

1.1.1 D´efinition de fonctions r´ecursives primitives . . . . . . . . . . . . . . . . .. 7

1.1.2 Exercices - quelques fonctions RP . . . . . . . . . . . . . . . . . . . . . . . 8

1.1.3 R´ealiser une fonction RP en un langage "actionnel" . . . . . . . . . . . . . 9

1.1.4 Quelques propri´et´es de fermeture de la classe RP . . . . . . . . . . . . . . . 9

1.2 Les pr´edicats RP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2.1 Exercices - des fonctions RP plus compliqu´ees . . . . . . . . . . . . . . . . 12

1.3 Les fonctions RP ne suffisent pas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3.1 Fonction d"Ackermann . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3.2 Interpr´eteur RP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4 Fonctions r´ecursives partielles . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 14

1.4.1 Minimisation non-born´ee . . . . . . . . . . . . . . . . . . . . . . . . . . . .15

1.4.2 Fonctions r´ecursives partielles et la th`ese de Church . . . . . . . . . . . .. 16

1.4.3 Exercices - fonctions r´ecursives partielles . . . . . . . . . . . . . . . . . . . 17

1.5 Machines de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.6 Th`ese de Church-Turing.´Equivalence MT - fonctions r´ecursives partielles . . . . . 19

1.6.1 Exercices - MT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.6.2 Vers la preuve de th´eor`eme 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.6.3 Exercices - G¨odelisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22

1.6.4 Fonction universelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.7 Th´eor`eme de la forme normale . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 23

1.8 Th´eor`eme de param´etrisation (s-m-n) . . . . . . . . . . . . . . . . . . . . .. . . . 24

1.8.1 Exercices - s-m-n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2 D´ecidabilit´e et ind´ecidabilit´e26

2.1 Probl`emes d´ecidables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26

2.2 Premiers probl`emes ind´ecidables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.2.1 Exercices sur la diagonalisation . . . . . . . . . . . . . . . . . . . . . . . .. 28

2.3 M´ethode de r´eduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.4 Semi-d´ecidabilit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 31

2.5 Ensembles r´ecursivement ´enum´erables (r.e.) . . . . . . . . . . . . . . . . . . . . .. 32

2.6 Semi-d´ecidabilit´e vs. r´eduction . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 35

2.7 Exercices - analyse de d´ecidabilit´e de probl`emes . . . . . . . . . . . . . . . . . .. 36

1

3 Applications de la calculabilit´e dans l"informatique 37

3.1 Probl`emes de v´erification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 37

3.1.1 Machines de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.1.2 Automate fini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.1.3 Machine `a pile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.1.4 Machine `a deux piles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.1.5 Exercice - Machine `a compteurs . . . . . . . . . . . . . . . . . . . . . . . . 39

3.1.6 Probl`emes pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.2 Probl`emes ind´ecidables dans la th´eorie de langages . . . . . . . . . . . . . . . .. . 40

3.2.1 Probl`emes relatives aux langages hors contexte . . . . . . . . . . . . . . .. 40

3.2.2 Syst`emes de r´e´ecriture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41

2

Pr´eface

Ce document contient les notes de cours et les exercices de TDs de la Calculabilit´e, que j"ai faits en 2000-2003 pour la maˆıtrise d"informatique `a l"Universit´e Joseph Fourier. En pr´eparant mon cours de la Calculabilit´e je me suis bas´e sur le cours fait`a l"UJF par Christian Boitet jusqu"`a 1999, et j"ai profit´e de ses conseils. Ce document n"aurait jamais vu le jour sans l"aide de deux jeunes chercheurs, Gerardo Schnei-

der, qui ´etant charg´e d"un groupe de TD en 2001, a assist´e `a tous les cours eta pris les notes tr`es

d´etaill´ees, et Thao Dang, qui a saisi ces notes en L ATEX.

Je remercie ´egalement les charg´es de TDs, qui ont beaucoup influenc´e le contenu et la forme

de mes cours. Ce sont (dans l"ordre chronologique) Peter Niebert, Gerardo Schneider, Christian

Boitet et Yassine Lakhnech.

Ce document dans sa forme actuelle est encore incomplet et certainement contient quelques

impr´ecisions. J"esp`ere de le compl´eter et de l"am´eliorer dans les mois qui viennent. Je serai re-

connaissant aux lecteurs pour leurs commentaires, remarques et suggestions constructives qu"ils peuvent m"envoyer `a l"adresseasarin@imag.fr

Eugene Asarin

Grenoble, avril 2003

Remarque

Actuellement je n"enseigne pas le cours de la Calculabilit´e, mais je laisse ce document sur ma

page web pour les ´etudiants et les enseignants qui peuvent le trouver utile. Je viens de corriger

quelques petites fautes, merci en particulier `a Ouri Maler qui m"a signal´e une impr´ecision concer-

nant les formes normales. Je serai toujours reconnaissant aux lecteurs pour leurs commentaires, qu"ils peuvent m"envoyer `a l"adresseasarin@liafa.jussieu.fr

Eugene Asarin

Paris, avril 2006

Notations typographiques

Le texte sur le fond gris repr´esente des raisonnements informels Les exercices sont donn´ees en utilisant cette police 3

Introduction0.1 Quelques exemples

Les cours d"informatique que vous avez eu peuvent donner une impression que pour chaque probl`eme on peut trouver un algorithme de solution. Dans le cours de la Calculabilit´e nous mon- trerons que ce n"est pas le cas et que pour des nombreux probl`emes naturels et int´eressantsil n"existe pas d"algorithme. Nous commencerons par quelques exemples illustratifs des probl`emes de d´ecision. Pour le moment nous ne donnons aucune preuve. Probl`eme de terminaison du programme "3x+ 1"Est-ce que le programme ci-dessous s"arrˆete sur unxdonn´e? whilex >1do{ if(xmod 2 = 0)thenx:=x/2; elsex:= 3x+ 1;

R´eponse.Pour ce probl`eme, on peut utiliser la proc´edure suivante : `a partir dexdonn´e ex´ecuter

ce programme, et s"il s"arrˆete retourner "OUI". Par contre, si pour un certainxle programme

"3x+1" boucle, cette proc´edure ne pourra jamais donner la r´eponse "NON". Une telle proc´edure

s"appelle unsemi-algorithme.

Il est inconnu s"il existe un algorithme de d´ecision pour ce probl`eme, qui pour chaquexdonn´e

renvoie une r´eponse correcte "OUI" ou "NON". Une conjecture dit que ce programme s"arrˆete

toujours. Si cette conjecture est vraie l"algorithme de d´ecision serait tout simplement de retourner

tout de suite "OUI" pour chaquex.

Probl`eme de terminaison de programmeC"est une g´en´eralisation du probl`eme pr´ec´edent.´Etant donn´e un texte d"une fonction (avec un argument entier) programm´e en Pascal et unx?N,

est-ce que cette fonction s"arrˆete pour l"argumentx? Pour ce probl`eme il existe un semi-algorithme (trouvez-le), mais il n"existe pas d"algorithme.

Probl`eme de correction de programme

´Etant donn´e un texte d"une fonction (avec un ar-

gument entier) programm´e en Pascal, est-ce que cette fonction calcule (par exemple) la factorielle.

Pour ce probl`eme il n"existe ni un algorithme, ni mˆeme un semi-algorithme. Donc le probl`eme

(tr`es pratique) si un programme donn´ee satisfait une sp´ecification n"admet pasd"algorithme de

d´ecision. Probl`eme de logique1.Est-ce qu"une formule propositionnelleFdonn´ee (telle queF=p? g?p? ¬p) est valide? R´eponse.Il existe des algorithmes pour ce probl`eme, par exemple,

- Algorithme 1 : Construire la table de v´erit´e. Si toutes les lignes contiennentseulement '1",

r´epondre "OUI". Si dans une ligne il y a '0" r´epondre "NON". - Algorithme 2 : DP (Davis-Putnam), vu en cours de Logique. 4 Probl`eme de logique2.Est-ce qu"une formule du premier ordre donn´ee (telle que par exemple ?xP(x)→ ?yP(y)) est valide?

R´eponse.Il n"existe pas d"algorithme g´en´eral (c-`a-d il n"y a pas d"algorithme qui donne la bonne

r´eponse pour une formule du premier ordre quelconque). La proc´edure vue en cours de Logique (`a

savoir, skol´emiser la n´egation de la formule, la mettre en forme clausale et appliquer la r´esolution)

peut ne pas terminer. Probl`eme de langages1.Pour une grammaire hors-contexte Γ, est-ce que son langage est vide, c-`a-dL(Γ) =∅? R´eponse.Il existe des algorithmes (vus en cours d"Automates et Langages). Probl`eme de langages2.Pour une grammaire hors-contexte Γ et un motw, est-ce quew?

L(Γ)?

R´eponse.Il existe des algorithmes (vus en cours d"Automates et Langages). Probl`eme de langages3.Pour deux grammaires hors-contexte Γ1et Γ2, est-ce queL(Γ1) =

L(Γ2)?

R´eponse.Il n"existe pas d"algorithme.

Probl`eme de langages4.Pour deux motsαetβet les r`egles de r´e´ecritureR(de la forme v→w), est-il possible de transformerαenβen appliquant plusieurs fois les r`eglesR?

R´eponse.Il n"existe pas d"algorithme.

0.2 Terminologie

Dans ce cours, nous allons consid´erer des probl`emes de d´ecision qui peuvent ˆetre formul´es

comme suit.´Etant donn´e un ensembleUde toutes les donn´ees possibles (un univers) et un ensemble

Bde toutes les donn´ees dites "bien" (B?U), pour chaque ´el´ementx?U, r´epondre "OUI" si x?Bet "NON" six??B. Par exemple, pour le probl`eme de logique 2

U={toutes les formules propositionnelles}

B={toutes les formules valides}.

Par abus de notation nous ´ecrirons ce probl`eme comme "x?B?", ou comme "B(x)?"

Voici une d´efinition informelle de probl`emes d´ecidables, semi-d´ecidables, ind´ecidables.

D´efinition 1Pour un probl`emeP= (U,B)donn´e, - Le probl`emePestd´ecidable?Il existe unalgorithmepourP(c"est-`a-dire une

proc´edure qui s"arrˆete et r´epond "OUI" si l"entr´eex?Bet r´epond "NON" si l"entr´ee

x??B). - Le probl`emePestind´ecidable?Il n"existepas d"algorithmepourP. - Le probl`emePestsemi-d´ecidable?Il existe unsemi-algorithmepourP(c"est-`a-dire une proc´edure telle que si l"entr´eex?Belle r´epond "OUI"; si l"entr´eex??Bdit "NON" ou ne donne pas de r´eponse). Il est clair qu"un probl`eme d´ecidable est aussi semi-d´ecidable.? Remarque.Pour montrer qu"un probl`eme estd´ecidable, il suffit de trouverun algorithme(un

seul suffit et ceci peut se faire sans utiliser la th´eorie de la calculabilit´e). Parcontre, pour montrer

qu"un probl`eme estind´ecidable, il faut consid´erertous les algorithmes possibleset montrer qu"aucun

d"eux ne r´esout le probl`eme, ce qui est plus difficile et impossible sans th´eorie et sans notion

rigoureuse d"algorithme. 5

0.2.1 Exercices - sans th´eorie

Pour chacun de probl`emes suivants donner explicitement leUet leB. Essayer de trouver - un algorithme de d´ecision; - `a d´efaut, un algorithme de semi-d´ecision ("un semi-algorithme"); - `a d´efaut, une opinion argument´ee, si un tel algorithme ou semi-algorithme existe. 1. ´Etant donn´e un grapheGet un entierk, y a-t-il une clique1de taillekdansG? 2. ´Etant donn´ee une ´equation quadratiqueax2+bx+c= 0aux coefficients entiers, est-ce qu"elle a une solution r´eelle? une solution enti`ere? 3.

´Etant donn´ee une ´equation alg´ebrique2`a une ou plusieurs variables et aux coefficients entiers,

est-ce qu"elle a une solution r´eelle? une solution enti`ere? R´efl´echissez d"abord `a la fa¸con de r´esoudre l"´equation x

66-15x62-2002 = 0ou bienx7-17xy+y5-9999 = 0.

4. ´Etant donn´ee la valeur initiale dex, est-ce que le programme suivant s"arrˆete : whilexmod5?= 0do ifxmod5 = 4 thenx:=x2+ 1 elsex:=x+ 2

5. C"est une l´eg`ere g´en´eralisation du probl`eme pr´ec´edent.

´Etant donn´ees la valeur initiale dexet la

valeur dey, est-ce que le programme suivant s"arrˆete : whilexmody?= 0do ifxmody=y-1 thenx:=x2+ 1 elsex:=x+ 2

6. Mˆeme question que pour 4 et 5

whilex?= 1do ifxmod2 = 0 thenx:=x/2 elsex:= 3x-1

0.3 Calculabilit´e vs Complexit´e

Nous repr´esentons une br`eve comparaison entre ces deux disciplines sous la forme d"un tableau

Calculabilit´eComplexit´e

Question :Existe-t-il un algorithme?Existe-t-il un algorithmerapide?

Hypoth`ese :

Ressources non-born´eesRessources born´ees

Technique 1 :

DiagonalisationDiagonalisation

Technique 2 :

R´eduction calculableR´eduction polynˆomiale

Le plan du cours

1. D´efinitions (rigoureuses) de la notion d"algorithme (mod`eles de calcul).

2. Propri´et´es g´en´erales des probl`emes (d´ecidabilit´e, ind´ecidabilit´e, m´ethode de preuve de l"ind´ecidabilit´e,

etc.)

3. Applications

1un sous-ensemble de sommets deGdont chaque deux ´el´ements sont reli´es par une arˆete

2une ´equation de la formeun polynˆome= 0

6

Chapitre 1

D´efinitions formelles de la notion

d"algorithme et mod`eles de calcul Notre but est de donner une d´efinition formelle de la classe de fonctions calculables. Cette d´efinition doit ˆetre `a la fois intuitive et correspondre `a la pratique de programmation. Une d´efinition simple est la suivante : une fonctionfest calculable s"il existe un algo- rithme pour la calculer. Puis, on peut envisager de d´efinir un algorithme par un pro- gramme PASCAL ou par un programme CAML.

L"inconv´enient de cette d´efinition est que la s´emantique de ces langages est tr`es compliqu´ee

(et peut varier d"une r´ealisation `a une autre) et, en plus, ces langages sont trop riches pour des

analyses th´eoriques. Pour cette raison nous d´efinirons les mod`eles de calculs et de "langages de

programmations" beaucoup plus simples, mais assez puissant pour d´ecrire n"importe quel algo- rithme. L"approche, que nous allons utiliser dans ce cours, est ditefonctionnelle. Nous allons restreindre notre attention aux algorithmes pour calculer les fonctions de la formef:Nk→N, et nous voulons aboutir `a une d´efinition (formelle) desfonctions calculablesf:Nk→N.

Pour voir le lien entre la d´ecidabilit´e et la calculabilit´e, consid´erons un probl`eme de d´ecision

(U,B) o`uU=Nk. Le probl`eme est donc le suivant : pourx?Ud´ecider six?B. Afin de d´ecider

si une entr´eex?B, nous allons utiliser lafonction caract´eristiquede l"ensembleB(d"entr´ees

"bien")χB(x) :U→N, qui est d´efinie comme suit.

D´efinition 2 (Fonction caract´eristique)

B(x) =?1six?B,

0sinon.

D´efinition 3Le probl`eme(U,B)est d´ecidable si et seulement siχBestcalculable.

Une fois que nous aurons une notion pr´ecise de fonction calculable, la d´efinition pr´ec´edente

deviendra aussi rigoureuse.

1.1 Fonctions r´ecursives primitives

Dans cette section nous faisons la premi`ere tentative de d´efinir la classe des fonctions cal- culables. On obtiendra une classe assez large, contenant presque tous les algorithmes que vous

connaissez, mais, n´eanmoins insuffisante. Dans les sections suivantes nous l"´elargirons encore.

1.1.1 D´efinition de fonctions r´ecursives primitives

D´efinition 4 (RP)La classe des fonction r´ecursives primitives (RP) est la classe de fonctions

f:Nk→Nd´efinie inductivement en utilisant3fonctions de base et2constructeurs suivants. 7 - Fonctions de base -Z´eroO:N0→Ntelle queO() = 0. -Successeurσ:N→Ntelle queσ(x) =x+ 1. -Projecteurπki:Nk→Ntelle queπki(x1,x2,...,xk) =xi. - Constructeurs -CompositionComp(f,g1,...,gk) =ht.q.h(¯x) =f(g1(¯x,...,gk(¯(x)). -Rec

Pri(f,g) =ut.q.?

u(¯x,0) =f(¯x) u(¯x,n+ 1) =g(¯x,n,u(¯x,n))

Autrement dit, la classe RP est la plus petite classe qui contient les fonctions debaseO,σ,πkiet

est ferm´ee par les constructeursCompetRec Pri. Exemple 1.Nous allons d´efinir la fonctionPlus(x,y) =x+y. D"abord,

Plus(x,0) =x

Plus(x,n+ 1) =Plus(x,n) + 1

Il suffit maintenant de r´ecrire les ´equations ci-dessus sous formeRec

Pri(f,g). Nous avons

Plus(x,0) =π11(x) =f(x)

Plus(x,n+ 1) =σ(π33(x,n,Plus(x,n))) =g(x,n,Plus(x,n))

Donc,Plus=Rec

Pri(π11,Comp(σ,π33)).?

Exemple 2.zero:λx.0 (avec un argument).

zero(0) = 0 =O() =f() zero(n+ 1) =zero(n) =π22(n,zero(n)) =g(n,zero(n))

Donc,zero=Rec

Pri(O,π22).?

Dans les deux s´eries d"exercices 1.1.2 et 1.2.1 nous ´etablirons la r´ecursivit´e primitive de nom-

breuses fonctions utiles.

1.1.2 Exercices - quelques fonctions RP

Montrer que les fonctions suivantes sont r´ecursives primitives (RP)en les construisant `a partir de

fonctions de base0,σ,πavec les constructeurs Comp et Rec Pri :

1. 7 (d"arit´e 0, c-`a-dλ.0et d"arit´e 1, c-`a-dλx.7);

2. Mult=λxy.x×y;

3.↑=λxy.x↑y(cela signifiexy);

4.λxy.x↑↑y(cela signifiex↑(x↑...↑x)?

yfois);

5.λx.sg(x)(signe :0quandxest nul,1quandxest positif);

6.λxy.x-y(diff´erence tronqu´ee ou monus :x-ysix≥y;0sinon);

7.λxy.|x-y|;

8. Montrer que la fonctiong=λx,y.2x+yest r´ecursive primitive en la construisant `a partir de

fonctions de base avec les constructeurs Comp et Rec Pri. 8 (a)plusest RP : ?plus(x,0) =x=π11(x) plus(x,n+ 1) =plus(x,n) + 1 =σ(plus(x,n)) =h(x,n,plus(x,n))

Donch=Comp(σ,π33)etplus=Rec

Pri(π11,Comp(σ,π33))

(b)exp2est RP : ?exp2(0) = 1 =σ(0) exp2(n+ 1) = 2n+1=exp2(n) +exp2(n) =h(n,exp2(n))

Donch=Comp(plus,π22,π22)

etexp2=Rec (c) Finalement,g=Comp(plus,Comp(exp2,π21),π22)

1.1.3 R´ealiser une fonction RP en un langage "actionnel"

Programmer les fonctions de base en un langage de programmation comme Pascalest trivial. En ce qui concerne la fonctionComp, si l"on sait programmerh(x1,...,xk) et g

1(¯x),...,gk(¯x), on peut alors programmerh(¯x) =f(g1(¯x),...,gk(¯x)). Pour la fonction

Rec, un programme pour la calculer est le suivant. fonctionu(x,y) r←f(x) fori= 0toy-1{ r←g(¯x,i,r) returnr On peut donc voir qu"une fonction RP est programmable en utilisant seulement des bouclesforimbriqu´es et les appels des fonctions non-r´ecursifs. Or, le langage RP est ´equivalent `a une partie du langage Pascal seulement avec la boucleforet sans appels r´ecursifs.?

1.1.4 Quelques propri´et´es de fermeture de la classe RP

D´ecrire les fonctions RP par des termes ne contenant que des fonctions de base et constructeurs

CompetRec

Priest une tˆache fastidieuse. Nous ´etablirons plusieurs propri´et´es de fermeture de la classe RP qui nous permettront d"´etablir la r´ecursivit´e partielle plus rapidement. Exemple.Consid´eronsf(n) =?ni=0i!. Afin de montrer que cette fonction est RP, notons d"abord quei! est RP puisqu"on peut l"exprimer comme ?0! = 1(i+ 1)! =i! (i+ 1)

Ensuite,fpeut ˆetre ´ecrite comme

?f(0) = 1 f(n+ 1) =f(n) + (n+ 1)!

La fonctionfest donc RP.?

Proposition 1Sig(¯x,i)est RP, alorsf(¯x,n) =?ni=0g(¯x,i)eth(¯x,n) =?ni=0g(¯x,i)sont aussi

RP. 9 Autrement dit, la classe de fonctions RP estferm´eepar rapport `a?et?. D´emonstration.Pour la somme?c"est un exercice. Pour le produit?, on peut ´ecrire la fonction hcomme suit.?h(¯x,0) =g(¯x,0) h(¯x,n+ 1) =h(¯x,n)·g(¯x,n+ 1) Puisqueget la multiplication·sont RP, la construction ci-dessus montre quehest aussi RP.

1.2 Les pr´edicats RP

Un pr´edicat surNkd´ecrit une propri´et´e d"unk-uplet (x1,...,xk). Il peut ˆetre d´efini par une

fonctionNk→ {vrai,faux}ou bien par un sous-ensemble deNk. Exemple 1.Le pr´edicatPairsurN. Nous avonsPair(5) =fauxetPair(6) =vrai. Le pr´edicat

Paircorrespond `a l"ensemble{0,2,4,6,8...}.

Exemple 2.Le pr´edicatPlusGrandsurN2est d´efini comme suit.

PlusGrand(x,y) =?vraisix > y,

fauxsinon. Il correspond `a un ensemble{(1,0),(2,0),...,(2,1),(3,1),...}. Dans le cadre d´efini dans l"introduction un pr´edicatPsurNkcorrespond au probl`eme (U,B) avecU=NketB={¯x|P(¯x)}.

D´efinition 5 (Fonction caract´eristique)SoitPun pr´edicat surNk. Sa fonction caract´eristique

estχP:Nk→Ntelle que

P(¯x) =?1siP(¯x),

0si¬P(¯x).

La fonction caract´eristique du pr´edicatPairest donc ?χPair(2n) = 1,

Pair(2n+ 1) = 0.

Et celle du pr´edicatPlusGrand

PlusGrand(x,y) =?1 six > y,

0 sinon.

D´efinition 6 (Pr´edicat RP)Un pr´edicatPsurNkest RP ssiχPest RP. Exemple 1.La fonction caract´eristique d"un pr´edicatPtel queP(x)?x?= 0 est :

P(x) =?1 six >0,

0 six= 0.

On peut voir queχP(x) =sg(x) etχPest donc RP. Par cons´equent, le pr´edicatPest RP.? Proposition 2SoientPetQdeux pr´edicats RP, alorsP?Q,P?Q,¬PetP?Qsont aussi RP. Autrement dit, la classe de pr´edicats RP estferm´eepar les op´erations bool´eennes. D´emonstration.Nous prouvons d"abord queP?Qest RP. Comme (P?Q)(¯x)≡P(¯x)?Q(¯x), alors, P?Q(¯x) =?1 siχP(¯x) = 1 etχQ(¯x) = 1,

0 sinon.

10

On peut en d´eduire queχP?Q(¯x) =χP(¯x).χQ(¯x). OrχPetχQsont RP par hypoth`ese et, de plus,

on sait que la multiplication est RP. Par cons´equent,χP?Qest RP etP?Ql"est aussi.

Nous allons maintenant prouver que¬Pest RP.

¬P(¯x) =?1 siχP(¯x) = 0,

0 siχP(¯x) = 1.

Il est facile de voir queχ¬P(x) = 1.-χP(¯x). Alors,χ¬Pest RP et¬Pest donc RP. Pour "?" et "?", on peut les exprimer en utilisant "?" et "¬" comme suit : (P?Q)≡ (¬(¬P? ¬Q)) et (P?Q)≡(¬(P? ¬Q)). Par la suite, nous pr´esentons les propri´et´es de la RP.

Il est important de noter que cette propri´et´e n"est pas vraie pour une quantification arbitraire,

par exemple?xP(¯x,y) ou bien?yP(¯x,y).

Q(¯x,n) =?

0 sinon.=n?

y=0χ

P(¯x,y)

On sait queχPest RP, par hypoth`ese. En plus, selon la Proposition 1, le produit?ny=0pr´eserve Proposition 4 (D´efinition par cas)Si les fonctionsgiet les pr´edicatsPisont RP (pouri? {1,...,n}, alors la fonction f(¯x) =? ?g

1(¯x)siP1(¯x),

gn(¯x)siPn(¯x). est aussi RP. Pour prouver la proposition, notons que la fonctionfpeut ˆetre ´ecrite commef=g1.χP1+...+ g n.χPn. Alors,fest RP puisqu"elle est obtenue `a partir des fonctions RP en utilisant l"addition et la multiplication. D´efinition 7 (Op´erateur de minimisation born´ee)SoitP(¯n,m)un pr´edicat. Alors,

0si un telin"existe pas.

On dit quefest obtenue dePpar la minimisation born´ee. Proposition 5 (Fermeture de RP par minimisation born´ee)SiPest RP, etfest obtenue dePpar la minimisation born´ee, alorsfest aussi RP

On peut d´efinir la fonctionfpar cas :

f(¯n,m) =?0 siP(¯n,0) f

1(¯n,m) sinon.

11 La fonctionf1(qui correspond au cas non-trivial de la minimisation quandP(¯n,0) est faux) peut ˆetre d´efinie par r´ecurrence primitive : ?f

1(¯n,0) = 0

f

1(¯n,m+ 1) =?

?f

1(¯n,m) sif1(¯n,m)>0

m+ 1 sif1(¯n,m)>0?P(¯n,m+ 1)

0 sinon

La premi`ere ligne du cas r´ecursif correspond au cas o`u le plus petitisatisfaisant la propri´et´e est

(et donc nous ne l"avions pas encore trouv´e aux ´etapes pr´ec´edentes, maisP(¯n,m+1)est vrai), la

derni`ere est pour le cas o`u nous ne trouvons pas le bonini avant, ni `a l"´etapem+ 1. Toutes les fonctions et pr´edicats qui interviennent dans la d´efinition def1sont RP, et, par cons´equent,f1l"est aussi. Doncfest aussi RP.

1.2.1 Exercices - des fonctions RP plus compliqu´ees

1. Montrer que les pr´edicatsx|y,EstPremier(x)etx mod y=zsont RP.

2.Nombres parfaits.Le nombrexest parfait s"il est ´egal `a la somme de tous ses diviseurs (diff´erents

dex). Par exemple :6 = 1 + 2 + 3,28 = 1 + 2 + 4 + 7 + 14. Montrer que le pr´edicatEstParfaitest r´ecursif primitif. Solution:Le pr´edicatestparfait(x)est r´ecursif primitif : est parfait(x) =" x=x-1X i=1i·χ|(i,x)# o`uχ|est la fonction caract´eristique du pr´edicat "divise".

3. Montrer que les fonctions suivantes sont r´ecursives primitives en utilisant les propri´et´es de fer-

meture : (a)xmody; (b)xdivy; (c)ex2(x): l"exposant de 2 dans la d´ecomposition dexen facteurs premiers; (d)px: lex-`eme nombre premier; Solution:On d´efinit la fonctionpnpar r´ecursion primitive ?p 0= 2 p n+1=μx <(n+ 2)2.x > pn? ?y < x(y= 1? ¬y|x)

Doncpnest r´ecursive primitivea

aOn a utilis´e l"in´egalit´epn<(n+ 1)2. (e)ex(x,y): l"exposant depxdans la d´ecomposition deyen facteurs premiers. (f)Cyx: le nombre de combinaisons dex´el´ementsy`ay; (g)?⎷ x?: la partie enti`ere de⎷x; (h)?logxy?: la partie enti`ere delogxy;

4. Les nombres de Fibonacci sont d´efinis par la r´ecurrence :

?Fib(0) = 1

Fib(1) = 1

Fib(n+ 2) =Fib(n) +Fib(n+ 1)

Montrer que la fonctionFibest RP.

12

1.3 Les fonctions RP ne suffisent pas

Nous avons vu dans que la classe de fonctions RP est assez riche pour d´efinir une grandemajo-

rit´e des algorithmes que vous connaissez. En choisissant une bonne repr´esentation de structures de

donn´ees par des entiers (les d´etails d"une tellearithm´etisationsont pareils que dans 1.6.2 ci-dessus)

il est possible de repr´esenter comme des fonctions RP les solutions de quasiment tous les probl`emes

vus en cours de Langages et Programmation. N´eanmoins, les deux exemples suivants montrent qu"il existe des fonctions calculables dans le sens informel (par exemple on peut les programmer en Pascal, CAML ou ADA), mais qui ne sont pas r´ecursives primitives. Ceci montre, que malgr´e

tout l"int´erˆet de la notion de fonctions RP, cette notionn"est pas une formalisation ad´equate de la

notion d"algorithme.

1.3.1 Fonction d"Ackermann

On consid`ere une famille de fonctions d´efinie comme suit. n↑0m=n·m=?n·0 = 0 n·(m+ 1) =n+n·m(1.1) n↑1m=?n↑0 = 1quotesdbs_dbs46.pdfusesText_46

[PDF] Algorithme suite algo 1ère Mathématiques

[PDF] algorithme suite algobox PDF Cours,Exercices ,Examens

[PDF] algorithme suite arithmétique PDF Cours,Exercices ,Examens

[PDF] algorithme suite casio PDF Cours,Exercices ,Examens

[PDF] algorithme suite casio graph 35+ PDF Cours,Exercices ,Examens

[PDF] Algorithme suite et limites Terminale Mathématiques

[PDF] algorithme suite exercice PDF Cours,Exercices ,Examens

[PDF] algorithme suite géométrique PDF Cours,Exercices ,Examens

[PDF] algorithme suite numérique PDF Cours,Exercices ,Examens

[PDF] algorithme suite numérique casio PDF Cours,Exercices ,Examens

[PDF] algorithme suite récurrente PDF Cours,Exercices ,Examens

[PDF] algorithme suite somme PDF Cours,Exercices ,Examens

[PDF] algorithme suite tant que PDF Cours,Exercices ,Examens

[PDF] algorithme suite terminale es PDF Cours,Exercices ,Examens

[PDF] algorithme suite terminale s PDF Cours,Exercices ,Examens