Calculabilité
Une fois que nous aurons une notion précise de fonction calculable la définition précédente deviendra aussi rigoureuse. 1.1 Fonctions récursives primitives.
Séance 5 : Fonctions récursives et machine de Turing
Définition V.1.2.2- Fonction calculable nous définissons dans cette partie la première classe des fonctions calculables. On obtiendra.
Calculabilité
Church-Turing et C est appelé l'ensemble des fonctions calculables. L'une des fonction est-elle calculable ou non calculable ?
Calculabilité et décidabilité
La thèse de Church 1 postule que tous ces modèles de calcul sont équivalents : une fonction calculable pour un modèle l'est pour un.
Toute fonction calculable est récursive
Théorème 1. 0 Soit f une fonction ?? ? ?? où ? et ? sont des alphabets. Si f est calculable par machine de. Turing
Initiation à la calculabilité
Jan 27 2017 nous pourrions alors définir toute fonction calculable. Hélas
Machine de Turing - Informatique Théorique 2 Licence 3 informatique
Turin ”On computable numbers
Machine de Turing =? ?-recursif
Savoir coder les fonctions de base en µ-récursif (voir appendice sur les On va montrer que toute fonction calculable par une machine de Turing est une ...
TD 05 – Réels Castor affairé
https://pageperso.lis-lab.fr/~kevin.perrot/documents/2018/calculabilite/TD05_18.pdf
La fonction du castor affairé nest pas calculable
On dit que cette fonction est calculable si il existe une machine de Turing unaire à un seul ruban bi-infini
[PDF] Calculabilité - Irif
La classe de fonctions calculables par machines de Tu- ring est égale `a la classe de fonctions calculables par un algorithme quelconque Pour prouver les deux
[PDF] Toute fonction calculable est récursive
Toute fonction calculable est récursive Manon Ruffini Théorème 1 0 Soit f une fonction ?? ? ?? où ? et ? sont des alphabets Si f est calculable par
[PDF] Séance 5 : Fonctions récursives et machine de Turing
Définition V 1 2 2- Fonction calculable Le problème (UB) est décidable si et seulement si ?B est calculable V 1 2 2 Fonctions récursives primitives
[PDF] Fonctions calculables et récursives - Léo Gayral
On dit que f est calculable si il existe une telle machine qui sur toute entrée ?n? (n ? I) termine avec ?f(n)? sur la gauche du ruban Par induction
[PDF] Calculabilité
Les fonctions peuvent être simples : l'addition ou la multiplication de deux entiers naturels ; ou plus compliquées : étant donné un entier naturel quelle est
[PDF] Cours de calculabilité et complexité
Fonctions calculable par les machines de Turing On peut réénoncé la th`ese de Church-Turing en termes de calcul de fonctions : Les fonctions calculables
[PDF] Initiation à la calculabilité - HAL
27 jan 2017 · On appelle fonction Turing-calculable les fonctions partielles (on peut avoir la valeur spéciale ?) ainsi définies Pour pouvoir définir des
[PDF] Éléments de Théorie de la Calculabilité
Il doit exister une fonction calculable f telle que f(n) est un code pour le n-ième algorithme qui calcule la n-ième fonction calculable fn Supposons
[PDF] Introduction `a la calculabilité - LACL
17 sept 2018 · Nous montrons dans cette section que les fonctions primitives récursives sont exac- tement les fonctions calculables par un programme structuré
[PDF] Initiation à la calculabilité - [Verimag]
24 fév 2013 · On appelle fonction Turing-calculable les fonctions partielles (on peut avoir la valeur spéciale ?) ainsi définies Pour pouvoir définir des
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
13 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
2Pr´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, ChristianBoitet et Yassine Lakhnech.
Ce document dans sa forme actuelle est encore incomplet et certainement contient quelquesimpr´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.frEugene Asarin
Grenoble, avril 2003
Remarque
Actuellement je n"enseigne pas le cours de la Calculabilit´e, mais je laisse ce document sur mapage 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.frEugene 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 3Introduction0.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ˆetetoujours. 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 2U={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 uneproc´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(unseul 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. 50.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 x66-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+ 25. 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+ 26. Mˆeme question que pour 4 et 5
whilex?= 1do ifxmod2 = 0 thenx:=x/2 elsex:= 3x-10.3 Calculabilit´e vs Complexit´e
Nous repr´esentons une br`eve comparaison entre ces deux disciplines sous la forme d"un tableauCalculabilit´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ˆomialeLe 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
6Chapitre 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´ecidersi 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 vousconnaissez, 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)). -RecPri(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 formeRecPri(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 g1(¯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) returnrquotesdbs_dbs45.pdfusesText_45[PDF] épaisseur atmosphère saturne
[PDF] fonction primitive récursive exercice corrigé
[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