[PDF] TD 2 – Fonctions récursives

View - Download TD 2 – Fonctions récursives

Previous PDF

Next PDF

Logique et complexité TD 2 M1 LMFI

TD 2 - Fonctions récursives

Exercice 1.Soitrla fonction définie parr(x) =z:(z2=x)etsla fonction définie par le schéma de récurrence

suivant : s(0) =r(0) s(n+ 1) =s(n) +r(n+ 1)

Que vaut la fonctions?

Solution de l"exercice 1.s(0) =r(0) = 0ets(1) = 0 +r(1) = 1, puiss(2) = 1 +r(2), maisr(2)n"est pas défini, doncs(2)n"est pas défini, ni toutes les valeurs suivantes des.

Exercice 2.

1. Décrire une machine de Turing calculant la fonctionn7!2n.

2. Décrire une machine de Turing calculant la fonctionn7! bn2

c.

3. Décrire une machine de Turing qui teste la relation de divisibilité.

Solution de l"exercice 2.Nous donnons ici une description de haut niveau du fonctionnement des machines.

Il serait possible mais fastidieux de décrire leurs états et leur fonction de transition.

1. Une stratégie possible est que la tête de lecture aille jusqu"au bout de l"entrée, puis écrive en alternant

des bâtons à gauche et à droite de cette position sur le ruban de sortie, jusqu"à retomber sur le symbole

de début de bande

2. La stratégie est la suivante. On définit une machine à trois bandes qui commence par recopier le contenu

de la première bande sur la 3ème bande. Ensuite, tant que la seconde bande n"est pas blanche, effacer

les deux "1" finaux sur la 3ème puis ajouter un "1" au second ruban (s"il ne reste qu"un "1" sur la 3ème

bande, l"effacer puis aller dans l"état final).

Il est maintenant facile d"écrire la table de transition d"une machine de Turing calculantn7! bn=2c. En

effet, on sait comparer deux nombres écrits en unaire sur deux bandes différentes, recopier une bande

sur une autre, effacer une bande qui contient un nombre écrit en unaire, tester si une bande contient

l"entier0, ainsi qu"incrémenter et décrémenter une valeur écrite en unaire sur un ruban. Ces briques de

base organisées selon l"algorithme décrit ci-dessus fournissent la description d"une machine de Turing

calculant la fonction demandée.

3. Même méthode qu"à la question précédente.

Exercice 3.Soitfune fonction totale deNdansN. Montrer quefest une fonction récursive si et seulement

si son graphe est récursif. Solution de l"exercice 3.SoitGfle graphe de f. Sif:N!Nest récursive totale, alorsGf(x;y) = R

=(y;f(x))est récursive comme composition de fonctions récursives et totale carfest totale. Réciproquement,

siGf(x;y)est récursive alorsf(x) =y((x;y)2Gf)est récursive par minimisation sur un ensemble récursif.

Exercice 4.Est-il vrai qu"une fonction totale est récursive primitive si et seulement si son graphe est récursif

primitif?

Solution de l"exercice 4.Si une fonction est récursive primitive, son graphe est récursif primitif. En effet,

(x1;:::;xp;y)est dans le graphe defssif(x1;:::;xp) =y.

La réciproque est fausse (comparer à l"exercice 3). Soitfune application deNdansNrécursive totale mais

non récursive primitive. Une telle fonctionfexiste, par exemplef(z) =A(12(z);22(z))oùAest la fonction

d"Ackermann vue en cours.

Cette fonctionfest calculée par machine de Turing : soitMune machine calculantf. Cette machine s"arrête

sur toute entrée. Soitt(x)le temps de calcul deMsur l"entréex. Le graphe detest récursif primitif. En effet,

soitil"indice deM:(x;y)est dans le graphe detssi(i;y;x)2B1, et on sait queB1est récursif primitif.

Supposons maintenant quetest récursif primitif. Alors la fonctionfle serait aussi (voir exercice 9), absurde.

Exercice 5.

1. Montrer que la fonctiongdéfinie parg(n) = 1s"il existe une suite denchiffres7consécutifs dans le

développement dep2,g(n) =?sinon est récursive.Université Paris Diderot 1 UFR de mathématiques

Logique et complexité TD 2 M1 LMFI

2. La fonctionhdéfinie parh(n) = 1sig(n) = 1eth(n) = 0sinon est-elle aussi récursive?

Solution de l"exercice 5.On peut montrer que cette fonction est récursive en faisant une discussion : soit il

existe dans le développement dep2des suites de7de longueur arbitraire, auquel cas la fonctiongdemandée

est la fonction constante1; soit il existe un entierkqui est la longueur maximale d"une suite de7et la fonction

gest la fonction valant1pour les entiers jusqu"àket?ensuite. dans les deux cas, la fonctiongest récursive.

Cette méthode fonctionne aussi pourh.

Autre méthode pourg: on utilise la fonctionf(m;i)(définie un exercice précédent) qui donne lai-ème décimale

depm. On a alors : g(n) =(

1 + 0(k(8i6n1;f(2;k+i) = 7))sin6= 0;

1sinon.

Cette méthode ne fonctionne pas pourh.

Exercice 6.

1. Montrer que l"image d"une fonction à une variable totale récursive et croissante est un ensemble récursif.

2. Réciproquement, montrer que tout ensemble récursif infini est l"image d"une fonction récursive strictement

croissante.

Solution de l"exercice 6.

1. Soitf2 F1récursive, totale, croissante. SiImfest fini,Imfest récursif primitif donc récursif. Si

Imfest infini on pose :Im(f)=R=(f(x(f(x)>y));y). La fonctionIm(f)est la composée de

fonctions récursives primitives et d"un schéma de minimisation appliqué à un ensemble récursif primitif.

DoncIm(f)est récursive. On note en outre que commefest totaleIm(f)est totale également si la

minimisation est définie, ce qui est le cas carImfest infini. On vérifie que la fonction définie dans le

membre de droite est bien la fonction caractéristique deImf:

1. si lexrenvoyé par la minimisation est tel quef(x) =yalorsy2Imf.

2. si lexrenvoyé par la minimisation est tel quef(x)> yalors8u < x;f(u)< ypar définition dex

et8u>x;f(u)>f(x)> ycarfest croissante, doncyn"est pas dans l"image def.

2. SoitENrécursif et infini. On pose :(

f(0) =min(E) f(n+ 1) =x(x > f(n) etx2E)

CommeEest un ensemble récursif,fest une fonction récursive (schéma de récurrence et schéma).

CommeEest infini, la fonctionfest totale. La fonctionfest strictement croissante. On vérifie facilement

queE= Imf.

Exercice 7.Soitfune fonction récursive totale deNdansNdont l"image est infinie. Montrer qu"il existe une

fonctiong, récursive totale, injective et ayant même image quef.

Solution de l"exercice 7.On commence par définir une fonctionqui énumère les points où la fonctionf

prend une valeur "pour la première fois".

Soitla fonction définie par :

(0) = 0 (n+ 1) =k(k > (n)et8i < k;f(i)6=f(k))

SoitE=feiji2N

touti. On montre facilement par récurrence que(i) =ei. Comme l"image defest infinie,Eest infini et la

fonctionest totale. Soitg=f. La fonctiongest récursive totale carfetsont récursives totales. Montrons quegest injective : supposonsg(k) =g(k0). On a(k) = minfxjf(x) =f((k))get(k0) = minfxjf(x) =f((k0))g. On on déduit(k) =(k0)et commestrictement croissante donc injective,k=k0.

Il reste à montrer quefetgont même image. Bien sûrIm(g)Im(f). Réciproquement, soity2Im(f). La

fonctionfprend cette valeur pour la première fois en un certainei=(i). On a doncy=g(i). On en déduit

Im(f)Im(g).

Exercice 8.Soitfune fonction récursive. Soitg(x)le plus petitz6xtel quef(z)diverge s"il existe un telz,

etg(x)non définie sinon. La fonctiongest-elle récursive?Université Paris Diderot 2 UFR de mathématiques

Logique et complexité TD 2 M1 LMFI

Solution de l"exercice 8.Sifest tout le temps définie, alorsgest la fonctoin nulle-part définie. Sinon, soit

tle plus petit entier pour lequelfn"est pas définie,g(x)est alors non-définie jusqu"àt1et vauttensuite.

Dans les deux casgest une fonction récursive.

Exercice 9.Montrer que sifest une application deNpdansNcalculable par une machine de Turing dont le

temps de calcul est une fonction récursive primitive de l"entrée(x1;:::;xp), alorsfest récursive primitive.

Solution de l"exercice 9.On a vu que toute fonction calculée par une machine de Turing est récursive et

est obtenue par une fonction récursive primitive appliquée aux arguments et au temps de calcul, doncfest

récursive primitive si le temps de calcul l"est.

Exercice 10.Le schéma de minimisation totale est le schéma obtenu en appliquant le schéma de minimisation

seulement dans le cas où il permet d"obtenir une fonction totale. SoitEle plus petit ensemble de fonctions

contenant les fonctions récursives primitives et clos par composition et minimisation totale. Montrer queEest

l"ensemble des fonctions récursives totales.

Solution de l"exercice 10.SoitTl"ensemble des fonction récursives totales. Pour montrer queE=Tnous

allons montrer les deux inclusions. Il est clair queE T, car les fonctions récursives primitives sont totales et

les schémas de composition et de minimisation totale n"introduisent pas de fonctions partielles.

Pour l"inclusionT E, il faut utiliser la preuve de l"équivalence entre fonctions récursives et fonctions calculables

par machine de Turing. En effet, sifest une fonction totale récursive, elle est calculée par une machine de turing.

L"expression de cette machine sous forme d"une fonction récursive ne fait intervenir que des compositions et des

fonctions récursives primitives, à part au moment où on calcule le temps de calcul, où on utilise une minimisation.

La fonctionfétant totale cette minimisation est un schéma de minimisation totale etfappartient donc àE.

Exercice 11.Dans cet exercice, nous considérons des machines de Turing avec les propriétés suivantes :

- Les machines ont deux rubans semi-infinis; - L"alphabet estf0;1;#g. Le symbole0est le symbole blanc et#est le symbole de début de bande (il n"apparaît que là).

On considère la fonction:N!Ndéfinie par :(n)est le maximum, sur toutes les machines de Turing comme

ci-dessus àn+ 1états, du nombre de1écrits au début de la seconde bande (avant le premier0) à la fin du

calcul, quand on lance cette machine sur l"entrée vide.

1. Montrer queest une application deNdansN(c"est-à-dire que pour toutn, il existe au moins une

machine àn+ 1états qui s"arrête sur l"entrée vide).

2. Montrer queest strictement croissante.

3. On veut montrer quen"est pas récursive. Dans la suite, on suppose par l"absurde qu"elle l"est. Montrer

que, sous cette hypothèse, la fonction:n7!(2n)est récursive totale.

4. Montrer qu"il exite une constantectelle que pour toutn2N, il existe une machine àn+cétats qui, sur

l"entrée vide, écrit111:::1|{z} (n)sur le second ruban.

5. Conclure par l"absurde quen"est pas récursive.

Exercice 12.Pour deux sous-ensemblesAetBdeN, on dit queAse réduit àB(ce qu"on noteA6B) si il existe une fonction récursive totaleftelle que pour toutx2N,x2Assif(x)2B.

1. Montrer que siBest récursif etA6B, alorsAest récursif.

2. Montrer que siBest récursivement énumérable etA6B, alorsAest récursivement énumérable.

Solution de l"exercice 12.

1. On aA=Bfdonc siBest récursif,Al"est aussi.

2. Soitbune fonction récursive partielle de domaineB. La fonctiona=bfa pour domaineAce qui

montre queAest récursivement énumérable. Exercice 13.SoitAun ensemble récursivement énumérable. On pose B=[ a2Adom('1a):

1. Montrer quef(a;x)2N2ja2Aet'1a(x)convergegest récursivement énumérable.

2. En déduire queBest récursivement énumérable.Université Paris Diderot 3 UFR de mathématiques

Logique et complexité TD 2 M1 LMFI

Exercice 14.Montrer que tout ensemble infini récursivement énumérable contient un sous-ensemble récursif

infini.

Solution de l"exercice 14.SoitAun sous-ensemble récursivement énumérable deN. Il est l"image d"une

fonction RPf(cours). On définit par schéma de récurrenceg:g(0)est le plus petit élément deA;g(n+ 1) =

f(k(f(k)> g(n))), ce qui est toujours défini carAest infini.gest donc croissante et son image est un

sous-ensemble deA. Par un résultat vu en TD, son image est récursive. Pour un sous-ensemble RE deNp, on

se ramène au cas précédent via le codagep. Exercice 15.Montrer que, siA;BNsont deux ensembles récursivement énumérables tels queA[B=N, alors il existe un ensemble récursifRNtel queRAetNnRB.

Solution de l"exercice 15.AetBsont tous deux récursivement énumérables, donc il existe deux machines de

TuringMetNtelles que les fonctions récursives qu"elles calculent prennent respectivementAetBcomme do-

maine de définition. On fait tourner les deux machinesMetNen parallèle sur une entréex; commeA[B=N,

on a toujours au moins une des deux machinesMetNqui s"arrête surx. Si c"estMqui s"arrête en premier

(ou que les deux machines s"arrêtent en même temps), alors on acceptex(autrement dit on renvoie1), dans le

cas contraire on rejettex(c"est-à-dire qu"on renvoie0).

Cela définit bien la fonction caractéristique d"un ensemble récursif car la machine ainsi obtenue s"arrête surx,

pour toutxappartenant àN. SoitRcet ensemble.

Six2R, alors la machine s"est arrêtée etMs"était arrêtée en premier sur la donnéex. DoncMs"arrête surx

etx2A. DoncRA.

Six2R, alors la machine s"arrête, et la machineMne s"était pas (encore) arrêtée. DoncNs"arrête surxet

x2B. DoncRB.

Voici une autre manière d"exprimer cette solution. Soitiun indice deA,jun indice deB(c"est-à-dire que

A=W1ietB=W1j). Alors on pose :

R(x) =B1

i; t(i;t;x)2B1ou(j;t;x)2B1; x

Cette fonction caractéristique est clairement récursive carB1est un ensemble récursif primitif et la minimisation

est une opération récursive. Elle est totale carA[B=N. On a donc bien construit un ensemble récursifRtel

queRAetRB.

Exercice 16.Soit'1la fonction récursive partielle à2variables permettant d"énumérer les fonctions récursives

partielles à1variable. Montrer qu"il n"existe pas de fonction récursive totalefprolongeant la fonctiongdéfinie

parg(x) ='1(x;x) + 1pour toutx2N.

Solution de l"exercice 16.Supposons qu"une telle fonctionfexiste. Alors elle a un indicei:f='1i. Mais

alorsf(i) ='1i(i)et cette valeur est donc définie carfest totale. Mais alorsgest définie eniet vaut'1i(i)+1

etfdevrait coïncider avec cette valuer, ce qui est une contradiction.

Exercice 17.

1. Montrer que tout sous-ensemble récursivement énumérable infini deNest l"image d"une fonction récursive

totale injective.

2. Peut-on demander en plus que cette fonction soit récursive primitive?

Solution de l"exercice 17.

1. On sait que tout ensemble récursivement énumérable deNnon vide est l"image d"une fonction récursive

primitive. Un exercice déjà vu montre alors que, comme l"ensemble est infini, il est l"image d"une fonction

récursive totale injective.

2. Rappelons quelques faits vus en cours sur la fonction d"Ackermann :

- Pour toutn;x,A(n;x)< A(n;x+ 1)etA(n;x)6A(n+ 1;x); - Pour toute fonctionfrécursive primitive deNdansN, il existen0telle quefest majorée parA(n0;)

à partir d"un certain rang.

SoitI=fA(x;x+1)jx2Ng. L"ensembleIest l"image d"une fonction récursive, c"est donc un ensemble

récursivement énumérable. CommeA(x;x+ 1)< A(x+ 1;x+ 2)pour toutx, l"ensembleIest infini.Université Paris Diderot 4 UFR de mathématiques

Logique et complexité TD 2 M1 LMFI

Supposons queIest l"image d"une fonction injective. Pour une infinité dex, on a(x)>A(x;x+1)(car

une fonctionhinjective deNdansNvérifieh(n)>npour une infinité d"entiersn; il suffit d"appliquer

ceci àh=g1oùgest définie parg(x) =A(x;x+ 1)).

Si on suppose en plus queest récursive primitive, elle est majorée à partir d"un certain rangBpar

A(n0;)pour un certainn0. Soitx >max(B;n0)tel que(x)>A(x;x+ 1). On a alorsA(x;x+ 1)6 (x)6A(n0;x)ce qui est absurde (carx>n0etx+ 1> x, et doncA(x;x+ 1)> A(n0;x)).

Exercice 18.On rappelle queB1est l"ensemble des triplets(i;t;x)tels que la machine d"indiceifonctionnant

sur l"entréexs"arrête au tempst. On considère la fonctiont:x7!y((x;y;x)2B1).

1. Montrer que la fonctiontest récursive et qu"elle n"est pas totale.

2. Montrer quetne peut pas être prolongée en une fonction récursive totale : il n"existe pas de fonction

récursive totaleftelle quetetfsoient égales sur le domaine de définition det.

Solution de l"exercice 18.

1. La fonctiontest récursive carB1est récursif primitif (résultat du cours) ettest obtenue par minimisation.

La fonctiontn"est pas totale car il existe des entiersxpour lesquels'1x(x)n"est pas défini, ce qui veut

dire quetne sera pas définie (c"est le cas par exemple pourxun indice de la fonction définie nulle part).

2. Supposons quetsoit prolongeable en une fonction totalef. Alors pour tester si un entierxappartient à

K=fx2Nj'1(x;x)#gil suffit de tester si(x;f(x);x)appartient àB1. En effet, sixappartient àK,

alorstest définie et doncfcoïncide avect, donc(x;f(x);x)appartient àB1. Par contre sixn"appartient

pas àK, alors comme le calcul'1x(x)ne s"arrête jamais,(x;f(x);x)n"appartient pas àB1, quelle que

soit la valeur que prendfenx. Exercice 19.SiA;BNsont deux ensembles tels queA\B=;, on dit queAetBsont récursivement séparables s"il existe un ensemble récursifRNtel queARetBR.

1. Donner un exemple deux ensemblesAetBrécursivement séparables.

2. SoitAetBdeux ensembles tels queA\B=;. On suppose queAetBsont récursivement énumérables.

Montrer queAetBsont récursivement séparables.

3. Montrer qu"il existe deux ensembles récursivement inséparables.

4. On souhaite montrer qu"il existe deux ensembles récursivement énumérables mais inséparables. Considérer

A=fi2Nj'1i(i) = 0getB=fi2Nj'1i(i) = 1get supposer queAetBsont récursivement séparables

par un ensemble récursifR. Considérer un indicerde la fonction caractéristique deRpour arriver à une

contradiction.

Solution de l"exercice 19.

1. SiAest récursif, alorsAetAsont récursivement séparés parA. On peut aussi prendref0getf1g.

2. Avec les hypothèses de la question, on a

AetBrécursivement énumérables et tels queA[B=N. Le résultat demandé s"obtient alors en appliquant l"exercice2de la feuille4.

3. SoitAun ensemble non récursif, alorsAetAne sont pas séparables, car cela impliquerait queAsoit

récursif.

4. Supposons d"abord quer2R. Alors'1r(r) = 1, doncr2B, ce qui est impossible carBest inclus dansR. Supposons maintenant quer62R. Alors'1r(r) = 0, doncr2A, ce qui est impossible carAest inclus

dansR. Exercice 20.Dans les cas suivants, donner un exemple d"ensembleAou montrer qu"il n"en existe pas (A désigne le complémentaire deA) :

1.Aest récursif etAest récursif.

2.Aest récursif etAn"est pas récursif.

3.Aest récursif etAest récursivement énumérable.

4.Aest récursif etAn"est pas récursivement énumérable.

5.Aest récursivement énumérable etAn"est pas récursif.

6.Aest récursivement énumérable etAest récursivement énumérable.

7.Aest récursivement énumérable etAn"est pas récursivement énumérable.

8.An"est pas récursivement énumérable etAn"est pas récursivement énumérable.Université Paris Diderot 5 UFR de mathématiques

Logique et complexité TD 2 M1 LMFI

Solution de l"exercice 20.

1. On peut prendreA=N, qui est récursif primitif donc récursif; et doncA=;, qui est aussi récursif

primitif.

2. SiAest récursif, alorsAest récursif. Ce n"est donc pas possible.

3. On peut à nouveau prendreA=N, qui est récursif primitif donc récursif; et doncA=;, qui est aussi

récursif primitif donc récursivement énumérable.

4. SiAest récursif, alorsAest récursif, donc récursivement énumérable. Ce n"est donc pas possible.

5. On peut prendreA=K, qui est bien récursivement énumérable, et dont le complémentaireKn"est pas

récursif.

6. SiAetAsont récursivement énumérables alorsAest récursif. Donc il suffit de poserA=N, et alorsA=;.

7. On peut prendre à nouveauA=K, qui est bien récursivement énumérable, et dont le complémentaireKn"est pas récursivement énumérable.

8. PosonsA= 2K[(1 + 2K).

Supposons queArécursivement énumérable. Sur une entréex, on peut tester "en parallèle" les deux

conditions2x2Aet2x+12A. L"un des deux calculs termine (puisquex2Koux2K). Ceci permet

d"obtenir un algorithme de décision pourK, ce qui est absurde car cet ensemble n"est pas récursif.

SiAest récursivement énumérable, on en déduit de même queKrécursif en testant en parallèle les

conditions2x2Aet2x+ 12A. Ceci montre que niAniAne sont récursivement énumérables. Exercice 21.Exhiber un ensemble récursifAN2tel que l"ensembleA0=fxj 8y2N;(x;y)2Agne soit pas récursivement énumérable.

Solution de l"exercice 21.Par définition deK,i2Ksi et seulement si'1i(i)diverge, c"est-à-dire si et

seulement si pour touttla machineisur l"entréeine s"arrête pas au tempst(ce qui s"écrit(i;t;i)2B1). Posons

A=f(i;t)2N2j(i;t;i)2B1g. L"ensembleA0=fi2Nj 8t2N;(i;t)2Ag=Kn"est pas récursivement énumérable alors queAest récursif carB1est récursif primitif.

Plus généralement, on peut prendre un ensemble récursivement énumérableXtel queXn"est pas récursivement

énumérable. AlorsXest la projection d"un ensemble récursifY:x2Xssi il existeytel que(x;y)2Y. Donc

x2Xssi pour touty,(x;y)2Y.Yest récursif maisXn"est pas récursivement énumérable.

Exercice 22.Montrer que le problème de déterminer sur l"entrée(x;y)sixappartient à l"image de'1yest

indécidable.

Solution de l"exercice 22.Il s"agit donc de montrer que l"ensembleBdes couples(x;y)tels quexappartient

à l"image de'1yn"est pas récursif. Mais si cet ensemble était récursif, alors tout sous-ensemble récursivement

énumérable deNserait récursif. En effet, soitAun ensemble récursivement énumérable. SiAest vide,Aest

récursif. SiAest non vide, alorsAest l"image d"une fonction récursivef, d"indicei. On en déduit quex2A

ssi(x;i)2B, doncAest récursif siBl"est. Exercice 23.Soitune fonction récursive totale injective deNdansN. SoitAl"image de. On pose :

B=fxjil existey > xtel que(y)< (x)g:

1. Montrer queBest récursivement énumérable et que son complémentaire est infini.

2. On suppose que le complémentaire deBcontient un ensemble récursivement énumérable infiniC. Montrer

queAest récursif.

Solution de l"exercice 23.

1.Best récursivement énumérable car il s"écrit comme un projection (un quantificateur existentiel) devant

un ensemble qui est récursivement énumérable (en fait récursif). Supposons que le complémentaire de

Bsoit fini. Alors il existex0tel que, pour toutx>x0,xappartient àB. C"est en particulier le cas de

x

0, donc il existex1> x0tel que(x1)< (x0).x1étant plus grand quex0,x1appartient àBet on

peut recommencer. On construit ainsi une suite infinie d"entiersxiqui est strictement croissante et telle

que(xi+1)< (xi). La suite des(xi)serait alors une suite d"entiers naturels infinie et strictement décroissante, ce qui est impossible.Université Paris Diderot 6 UFR de mathématiques

Logique et complexité TD 2 M1 LMFI

2. On veut pouvoir tester si un entierxappartient à l"image de. Si on peut trouver un entiery2B

tel que(y)>xalors on pourra faire ce test. En effet, siy2B, alors pour toutz > yon sait que (z)> (y)>xet doncxne peut être l"image d"un entier plus grand quey, ce qui nous laisse juste à

tester les images des entiers jusqu"ày. Pour pouvoir trouver un telyon va utiliser le fait queBcontient

un sous-ensemble récursivement énumérable infiniC: celui-ci est alors l"image d"une fonction totale

récursivef. Soitb(x) =f(k((f(k))>x)). Cette fonction est totale car l"image def(l"ensembleC) est infinie et

elle renvoie une valeurycomme celle souhaitée par la discussion ci-dessus. On peut alors montrer queA

est récursif :x2Assi9u6b(x) ((u) =x). Exercice 24.Montrer qu"il existeANvérifiant les deux propriétés suivantes : - le complémentaire deAest infini;

-Aintersecte tout ensemble récursivement énumérable infini.Université Paris Diderot 7 UFR de mathématiques

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