-Logique-mathematique-Tome-II-Rene-Cori.pdf

Logique mathmatique

Cours et exercices Il. Fonctions rcursives, thorme de Gdel, thorie des ensembles, thorie des modles

CHEZ LE MME DITEUR

Des mmes auteurs : LOOIQUE MATHMATIQUE. COURS ET EXERCICES, parR. CORI et D. LASCAR. Prface de

J.-L. KRIVINE. Collection Axiomes. Tome 1.- Calcul propositionnel, algbres de Boole, calcul des prdicats. 1993,408 pages.

Dans la mme collection : LE THORME D'INCOMPLTIJDE DE GDEL, par R.M. SMULL Y AN. Traduit de l'anglais par

M. MARGENS1ERN. 1993, 160 pages environ, paratre.

Dans la collection Logique, Mathmatiques, Informatique: SYSTMES FORMELS. INIRODUCTION LA LOOIQUE ET LA THORIE DES LANGAGES, par

C. BENZAIN. 1991, 184 pages. ALGORITIIMIQUE ALGBRIQUE, avec exercices corrigs, par P. NAUDIN etC. QUITT. 1992,

480 pages. MATHMATIQUES DISCR1ES ET INFORMATIQUE, par N.H. XUONG. 1992, 432 pages. ALGORITHMES ET COMPLEXIT, par H.S. WILF. Traduit de l'anglais par P. ROUX. 1989,

208 pages.

Dans la collection ER/ : LOOIQUE, RDUCTION, RSOLUTION, par R. LALEMENT. Prface de M. DEMAZURE. 1990,

384 pages. LAMBDA-CALCUL, TYPES ET MODLES, par J.-L. KRIVINE. 1990, 184 pages. LOGIQUE TEMPORELLE. Smantique et validation de programmes parallles, par

E. AUDUREAU, P. ENJALBERT et L. FARINAS DEL CERRO. Prface de E. ENGELER. 1990, 240 pages.

OUTILS LOGIQUES POUR LE TRAI1EMENT DU 1EMPS. De la linguistique l'intelligence artificielle, par H. BESTOUGEFF et G. LIGOZAT. 1989, 272 pages.

TRANSDUCTIONS RATIONNELLES. Application aux langages algbriques, par J.-M. AU1EBERT et L. BOASSON. 1988, 136 pages.

Dans la collection MIM-Algorithmique, Programmation : PROGRAMMATION EN LOGIQUE, parC. J. HOGGER. Traduit de l'anglais parR. QUINIOU.

Prface deR. KOWALSKI. 1987,296 pages. LOGIQUES POUR L'INTELLIGENCE ARTIFICIELLE, parR. TURNER. Traduit de l'anglais par

Ph. BESNARD. 1987,296 pages. CALCULABILIT ET DCIDABILIT, par J.-M. AU1EBERT. 1992, 120 pages.

Autres ouvrages : LES ARBRES ET LES REPRSENTATIONS DES PROXIMITS, par J.-P. BARTHLMY et

A. GUNOCHE. Prface de M. MINOUX. Collection Mthode + Programmes. 1988, 256 pages.

AXIOMES Collection de logique mathmatique coordonne par J. -L. KR/VINE

Logique mathmatique

Cours et exercices Il. Fonctions rcursives, thorme de Gdel, thorie des ensembles, thorie des modles

Ren CORI Assistant l'universit Denis Diderot (Paris 7)

Daniel LASCAR Directeur de recherches au CNRS

Prface de J.-L. KRIVINE

2e tirage corrig

MASSON Paris Milan Barcelone 1994

Illustration de couverture : Collection Viollet.

Ouvrage rdig avec le concours du ministre de la Recherche et de l'Espace (DIST).

Tous droits de traduction, d'adaptation et de reproduction par tous procds, rser-vs pour tous pays.

Toute reproduction ou reprsentation intgrale ou partielle, par quelque procd que ce soit des pages publies dans le prsent ouvrage, faite sans l'autorisation de l'diteur, est illicite et constitue une contrefaon. Seules sont autorises, d'une part, les reproductions strictement rserves l'usage priv du copiste et non destines une utilisation collective, et d'autre part, les courtes citations justifies par le caractre scientifique ou d'information de l'uvre dans laquelle elles sont incorpores (art. L. 122-4. L. 122-5 et L. 335-2 du Code de la proprit intellectuelle).

Des photocopies payantes peuvent tre ralises avec l'accord de l'diteur. S'adres-ser au : Centre franais d'exploitation du droit de copie, 3, rue Hautefeuille, 75006 Paris, tl. : 43.26.95 35.

MASSON S.A. MASSON S.p.A. MASSON S.A.

Masson, Paris, 1993

ISBN: 2-225-84080-6 ISSN : 1243-4264

120, bd Saint-Germain, 75280 Paris Cedex 06 Via Statuto 2/4, 20121 Milano Avenida Principe de Asturias 20,08012 Barcelona

PREFACE

La logique est, en France, une discipline traditionnellement nglige dans les tudes scientifiques universitaires. Cela tient, sans doute, l'histoire rcente des mathmatiques dans notre pays, domines pendant longtemps par l'cole Bourbaki, dont, comme on sait, la logique n'tait pas le fort. La logique part, en effet, d'une rflexion sur l'activit mathmatique, et une raction pidermique courante du mathmaticien est de dire: A quoi bon tout cela? nous ne sommes pas des philosophes, et ce n'est pas en se cassant la tte sur le modus panens ou le tiers exclu que l'on rsoudra les grandes conjectures, ni mme les petites. Voire ... Cependant un lment nouveau, et de taille, est venu clore ce dbat un peu byzantin sur l'intrt de la logique : l'explosion de l'informatique, dans tous les domaines de la vie conomique et scientifique, dont l'onde de choc a fini par atteindre les mathmaticiens eux-mmes. Et petit petit, une vidence se fait jour : pour cette nouvelle science en train de natre, les bases thoriques ne sont autres que cette discipline si discute : la logique mathmatique. Il est vrai que certains domaines de la logique ont t mis contribution plus vite que d'autres. Le calcul boolen, bien sr, pour la conception et l'tude des circuits ; la rcursivit, qui est la thorie des fonctions calculables sur machine ; le thorme de Herbrand, la rsolution et l'unification, qui sont la base de la programmation dite logique (langage PRO LOG) ; la thorie de la dmonstration, et les divers avatars du thorme de compltude, qui se rvlent de puissants outils d'analyse pour les langages de programmation volus ... Mais, au train o vont les choses, on peut penser que le tour ne saurait tarder venir, mme pour des domaines rests encore compltement purs , comme la thorie des ensembles, par exemple. Comme il se doit, l'interaction n'est pas sens unique, loin de l, et un afflux d'ides et d'intuitions nouvelles et profondes, issues de l'informatique, est venu renouveler tous ces secteurs de la logique. Cette discipline est maintenant l'une des plus vivantes qui soient en mathmatiques, et en volution trs rapide. Aussi l'utilit et l'actualit d'un ouvrage d'initiation gnrale en logique ne font-elles pas de doute, et ce livre vient donc son heure. Issu d'un enseignement du D.E.A. de

VI Prface

Logique et fondements de l'Informatique l'Universit Paris 7, il couvre un vaste panorama: algbre de Boole, rcursivit, thorie des modles, thorie des ensembles, modles de l'arithmtique et thormes de Gdel. La notion de modle est un lment central de l'ouvrage, et c'est fort juste titre, car elle a aussi une place centrale en logique : malgr (ou grce ) son caractre simple et mme lmentaire, elle en claire tous les domaines, y compris ceux qui en paraissent les plus loigns. Comment comprendre, par exemple, une dmonstration de consistance en thorie des ensembles, sans avoir d'abord matris le concept de modle de cette thorie? comment saisir vraiment le thorme de Gdel sans avoir une ide sur les modles non standard de 1' arithmtique de Peano ? L'acquisition de ces notions smantiques est, je le crois, caractristique d'une vritable formation de logicien, quelque niveau que ce soit. R. Cori et D. Lascar le savent fort bien, et leur livre va tout fait dans ce sens. Qui plus est, ils ont russi le difficile pari d'allier toute la rigueur ncessaire avec la clart, le souci pdagogique et l'agrment de la lecture. Nous disposons donc l d'un outil remarquable pour l'enseignement de la logique mathmatique, et, vu le dveloppement de la demande en ce domaine, il devrait connatre un franc succs. C'est, bien sr, tout ce que je lui souhaite.

Paris, le 4 Novembre 1992 Jean-Louis Krivine

TABLE DES MATIERES DU TOME 1

Prface . . . . . . . . . Table des matires du tome 1 Table des matires du tome II Contents

Avant-propos Introduction . Mode d'emploi

Chapitre 1 : Calcul propositionnel 1. Syntaxe . . . . . . .

Les formules propositionnelles Dmonstrations par induction sur l'ensemble des formules Arbre de dcomposition d'une formule . . . . . Le thorme de lecture unique . . . . . . . . Dfinitions par induction sur l'ensemble des formules Substitutions dans une formule propositionnelle

2. Smantique . . . . . . . . . . . . . . Distributions de valeurs de vrit, tables de vrit Tautologies, formules logiquement quivalentes Quelques tautologies . . . . . . . . . . .

3. Formes normales, sxstmes complets de connecteurs Oprations dans {0,1} et formules . . . . . .

Formes normales . . . . . . Systmes complets de connecteurs

4. Lemme d'interpolation . . . Thorme de dfinissabilit

5. Thorme de compacit Satisfaction d'un ensemble de formules Le thorme de compacit du calcul propositionnel

Exercices . . . . . . .

Chapitre 2 : Algbres de Boole 1. Rappels d'algbre et de topologie

Algbre . . . . . . . . . Topologie . . . . . . . . Application au calcul propositionnel

2. Dfinition des algbres de Boole . . . . . Proprits des anneaux de Boole, relation d'ordre . Les algbres de Boole en tant qu'ensembles ordonns

v

VIl

x

Xlii

1 3

11

15 17 17 21 23 25 28 29 32 32 38 42 46 46 50 53 55 57 59 59 62 68

79 81 81 84 90 91 91 95

VIII Table des matires du tome 1

3. Atomes dans une algbre de Boole . . . . . 4. Homomorphismes, isomorphismes, sous-algbres

Homomorphismes et isomorphismes . . . . Sous-algbres de Boole

5. Idaux et filtres Proprits des idaux Idaux maximaux Filtres Ultrafiltres . . . . Bases de filtre

6. Le thorme de Stone . L'espace de Stone d'une algbre de Boole Le thorme de Stone . . . . . . . . Les espaces boolens sont des espaces de Stone

Exercices . . . . . . . .

Chapitre 3 : Calcul des prdicats 1. Syntaxe . . . . . . .

Langages du premier ordre Les termes du langage Les substitutions dans les termes Les formules du langage . . . . Variables libres, variables lies, formules closes Les substitutions dans les formules

2. Les structures . . . . . . Les ralisations d'un langage . . Sous-structures, restrictions Homomorphismes, isomorphismes

3. Satisfaction des formules dans les structures Interprtation des termes du langage dans une structure Satisfaction des formules du langage dans une structure Equivalence universelle et consquence smantique

4. Formes prnexes et formes de Skolem Formes prnexes . . . . . . Formes de Skolem . . . . . . .

5. Premiers pas en thorie des modles Satisfaction dans une sous-structure Equivalence lmentaire . . . . Langage associ une structure, formules paramtres Relations et fonctions dfinissables dans une structure

6. Modles non galitaires Exercices . . . . . .

Chapitre 4 : Thormes de compltude 1. Dmonstrations formelles . . .

Rgles et axiomes . . . . . Dmonstrations formelles Thorme de finitude et lemme de dduction

99 101 101 106 109 109 112 114 115 118 120 121 125 126 130

137 139 139 141 148 149 152 155 158 160 162 164 167 167 170 177 188 188 191 197 197 201 207 210 213 216

227 229 229 232 235

Table des matires du tome 1

2. Les modles de Henkin Les tmoins de Henkin Le thorme de compltude

3. La mthode de Herbrand . Quelques exemples . . . . Les avatars d'une formule .

4. Les dmonstrations par coupure La rgle de coupure Compltude de la mthode

5. La mthode de rsolution . Unification . . . . . Les dmonstrations par rsolution

Exercices . . . . . . . .

Solutions des exercices du tome 1 Chapitre 1 Chapitre 2 Chapitre 3 Chapitre 4

Bibliographie Notations Index

IX

238 238 241 245 245 248 254 254 257 261 261 267 277

281 282 305 326 350

361 365 373

TABLE DES MATIERES DU TOME II

Prface . . . . . . . . . Table des matires du tome I Table des matires du tome II Contents

Avant-propos Mode d'emploi

Chapitre 5: Rcursivit 1. Fonctions et ensembles rcursifs primitifs

Les premires dfinitions Exemples et proprits de clture Codages des sui tes . . .

2. Fonctions rcursives . . . . . . La fonction d' Ackermann Le schma pet les fonctions partielles rcursives

3. Machines de Turing . . . . . . . . . . . . Description des machines de Turing . . . . . Les fonctions T -calculables . . . . . . . . Les fonctions partielles T -calculables sont rcursives Machines de Turing universelles . . . . . .

4. Les ensembles rcursivement numrables Ensembles rcursifs et rcursivement numrables Le thorme smn Les thormes de point fixe

Exercices . . . . . . . . .

Chapitre 6: Formalisation de l'arithmtique- Thormes de Gdel 1. Les axiomes de Peano

Les axiomes L'ordre sur les entiers

2. Les fonctions reprsentables 3. Arithmtisation de la syntaxe

Codage des formules Codage des dmonstrations

v

VIl

x

Xlii

1 3

7 9 9

11 15 18 18 22 26 26 28 33 37 41 41 47 51 55

65 67 67 72 76 81 81 85

Table des matires du tome Il

4. Les thorms d'incompltude et d'indcidabilit . . . . Indcidabilit de l'arithmtique et du calcul des prdicats Les thormes d'incompltude de Godel

Exercices . . . . . . . . .

Chapitre 7 : Thorie des ensembles 1. Les thories Z et ZF . . . .

Les axiomes . . . . . . Couples, relations et applications

2. Les ordinaux et les entiers Ensembles bien ordonns Les ordinaux . . . . . Oprations sur les ordinaux Les entiers . . . . . . .

3. Dmonstrations et dfinitions par induction L'induction L'axiome du choix .

4. Cardinalit . . . . Les classes cardinales Oprations sur les classes cardinales Les cardinaux finis Le dnombrable . . . . . . . . Les cardinaux . . . . . . . .

5. L'axiome de fondation et le schma de rflexion L'axiome de fondation . . . . . . . Quelques rsultats de consistance relative Cardinaux inaccessibles Le schma de rflexion

Exercices . . . . . . .

Chapitre 8: Un peu de thorie des modles 1. Sous-structures et extensions lmentaires

Sous-structures lmentaires . . . Le test de Tarski-Vaught . . . .

2. Construction d'extensions lmentaires Applications lmentaires . . . . La mthode des diagrammes

3. Les thormes d'interpolation et de dfinissabilit 4. Produits rduits et ultraproduits 5. Thormes de prservation

Prservation par sous-structure Prservation par union de chane Prservation par produit rduit .

Xl

91 91 93

103

111 113 113 120 125 125 127 135 139 141 141 144 147 147 150 153 157 160 167 167 170 174 176 181

189 191 191 195 197 197 199 205 211 216 216 219 223

Xli

6. Les thories aleph-zro-catgoriques Le thorme d'omission des types Structures aleph -zro-catgoriques

Exercices . . . . . . . .

Solutions des exercices du tome II Chapitre 5 Chapitre 6 Chapitre 7 Chapitre 8

Bibliographie Notations Index

Table des matires du tome Il

227 227 233 239

249 250 267 279 300

323 327 335

CONTENTS

VOLUME!

Foreword Introduction . . . How to use the book

Chapter 1 : Propositional calculus . . . . . . . . . . . . 1. Syntax . . . . . . . . . . . . 2. Semantics . . . . . . . . . . . . 3. Normal forms and complete systems of connectives 4. Interpolation lemma 5. Compactness theorem

Exercises . . . . . . . .

Chapter 2 : Boolean algebras . . . . . . 1. Review in algebra and topology 2. Definition of Boolean algebras . 3. Atoms in a Boolean algebra 4. Homomorphisms, isomorphisms, subalgebras 5. Ideals and filters 6. Stone theorem

Exercises . . . . .

Chapter 3 : Predicate calculus . . . . . . . . . 1. Syntax . . . . . . . . . 2. The structures . . . . . . . . . 3. Satisfaction of formulas in structures 4. Prenex forms and Skolem forms 5. First steps in madel theory 6. The predicate of identity

Exercises . . . . . . . . . .

1 3

11

15 17 32 46 55 59 68

79 81 91 99

101 109 120 130

137 139 158 167 188 197 213 216

XIV

Chapter 4 : Completeness theorems 1. Formai proofs . . 2. Henkin's models 3. Herbrand's method 4. The resolution method in propositional calculus 5. The resolution method in predicate calculus

Exercises . . . . . . . . . . . . . . . . . .

Answers to the exercises of chapters 1-4 Chapter 1

Bibliography Notations Index

VOLUME II

Chapter 2 Chapter 3 Chapter 4

Foreword . . . . How to use the book

Chapter 5 : Recursion theory . . . . . . . . . 1. Primitive recursive functions and sets 2. Recursive functions . . . 3. Turing machines . . . . 4. Recursively enumerable sets

Exercises . . . . . . . . . .

Chapter 6 : Formalization of arithmetic, Gdel theorems 1. Peano's axioms 2. Representable functions . . . . . . 3. Arithmetic of syntax . . . . . . 4. Incompleteness and undecidability theorems

Exercises . . . . . . . . . . . . . . . . .

Contents

227 229 238 245 254 261 277

281 282 305 326 350

361 365 373

1 3

7 9

18 26 41 55

65 67 76 81 91

103

Contents

Chapter 7 : Set theory . . . . . . . . . . 1. The theories Z and ZF 2. Ordinal numbers and integers . 3. Inductive proofs and definitions 4. Cardinality . . . . . . . . . 5. The regularity axiom and the reflection scheme

Exercises . . . . . . . . . . . . . . . . . .

Chapter 8 : Sorne model theory . . . . . . . . . . . 1. Elementary substructures and extensions 2. Construction of elementary extensions 3. The interpolation and definability theorems 4. Reduced products and ultraproducts 5. Preservation theorems . . . . . 6. The aleph-zero-categorical theories

Exercises . . . . . . . . . . . . .

Answers to the exercises of chapters 5-8 Chapter 5

Bibliography Notations Index

Chapter 6 Chapter 7 Chapter 8

xv

111 113 125 141 147 167 181

189 191 197 205 211 216 227 239

249 250 267 279 300

323 327 335

Ce livre est ddi l'ducation et la gographie physiques.

R.C. et D.L.

A V ANT- PROPOS

Ce livre fait suite une exprience de plusieurs annes d'enseignement de la logique l'U.F.R. de Mathmatiques de l'Universit Paris 7, tant en deuxime cycle que dans le D.E.A. de Logique et Fondements de l'Informatique.

Ds que nous avons commenc prparer nos premiers cours, nous avons constat qu'il allait tre bien difficile d'indiquer nos tudiants des ouvrages gnraux de logique crits (ou mme traduits) en franais. Nous avons alors dcid de profiter de l'occasion qui nous tait donne de remdier cela. Les premires versions des huit chapitres qu'on va lire ont donc t rdiges en mme temps que leur contenu tait enseign. Nous tenons remercier chaleureusement tous les tudiants qui ont ainsi contribu une amlioration sensible de l'expos initial.

Nos remerciements vont aussi tous nos collgues et amis logiciens, de Paris 7 ou d'ailleurs, qui nous ont apport une aide trs apprcie, par leurs nombreuses remarques et par un soutien moral d'une rare qualit. Presque tous sont co-auteurs de cet ouvrage, puisque, pour constituer les listes d'exercices qui accompagnent chaque chapitre, nous avons puis sans retenue dans le fonds inestimable que reprsentent les centaines et centaines de textes qui ont t proposs aux tudiants, pendant plus de vingt-cinq annes, au cours desquelles l'Universit Paris 7, pionnire en la matire, a organis des enseignements de logique ouverts un large public.

Parvenu ce stade, le lecteur s'attend en gnral une phrase du type suivant : ils sont tellement nombreux que nous ne pouvons videmment pas les citer tous. En effet, ils sont trs nombreux, ceux qui va notre gratitude, mais pourquoi ne pas essayer de les citer tous ?

Merci, donc, Josette Adda, Marouan Ajlani, Daniel Andler, Gilles Amiot, Fred Appenzeller, Jean-Claude Archer, Jean-Pierre Azra, Jean-Pierre Bnjam, Chantal Berline, Claude-Laurent Bernard, Georges Blanc, Elisabeth Bouscaren, Albert Burroni, Jean-Pierre Calais, Zo Chatzidakis, Peter Clote, Franois Conduch, Jean Coret, Maryvonne Daguenet, Vincent Danos, Max Dickmann, Patrick Dehornoy, Franoise Delon, Florence Duchne, Jean-Louis Duret, Marie-Christine Ferbus, Jean-Yves Girard, Danile Gondard, Catherine Gourion, Serge Grigorieff, Ursula Gropp, Philippe Ithier, Bernard Jaulin, Ying Jiang, Anatole Khlif, Georg Kreisel, Jean-Louis Krivine, Ramez Labib-Sami, Daniel Lacombe, Thierry Lacoste, Richard Lassaigne, Yves Legrandgrard,

2 Avant-propos

Alain Louveau, Franois Lucas, Kenneth Mac Aloon, Gilles Macario-Rat, Sophie Malecki, Jean Malifaud, Pascal Manoury, Franois Mtayer, Marie-Hlne Mourgues, Catherine Muhlrad-Greif, Francis Oger, Michel Parigot, Donald Pelletier, Marie-Jeanne Perrin, Bruno Poizat, Jean Porte, Claude Prcetti, Christophe Raffalli, Laurent Rgnier, Jean-Pierre Ressayre, Philippe Royer, Paul Rozire, Gabriel Sabbagh, Claire Santoni, Marianne Simonot, Gerald Stahl, Jacques Stern, Anne Strauss, Claude Sureson, Jacques Van de Wiele, Franoise Ville.

Nous tenons aussi rendre hommage au travail administratif et technique remarquable accompli par Mesdames Sylviane Barrier, Gisle Goeminne et Claude Orieux.

Que ceux que nous avons oublis nous pardonnent. Ils sont tellement nombreux que nous ne pouvons les citer tous.

Septembre 1993:

- Les coquilles et erreurs dans le premier tirage taient tellement nombreuses que mme Alain Kapur n'a pu les relever toutes. Qu'il soit assur de tous nos encouragements pour la lourde tche qui l'attend encore.

Nous remercions galement Edouard Dorard et Thierry Joly pour leur lecture trs attentive.

- Selon des sources dignes de foi, le Mercredi 23 Juin 1993, Andrew Wiles a fait perdre l'exercice 6 du chapitre 6 une bonne partie de son intrt. Nous ne lui en voudrons pas trop.

MODE D'EMPLOI

Le livre est organis en deux tomes. Le premier comporte les chapitres 1 4, le second les chapitre 5 8. Les notions exposes dans un chapitre donn supposent connues celles qui ont fait l'objet des chapitres antrieurs (mais les chapitres 2 et 5 font exception cette rgle).

Chacun des huit chapitres est divis en sections, elles-mmes composes d'un certain nombre de sous-sections, numrotes de la faon la plus simple qui soit : 2.3 annonce le dbut de la troisime sous-section de la section 2. Les dfinitions, lemmes, propositions, thormes, corollaires et remarques sont identifis par la sous-section dans laquelle ils figurent ; lorsqu'il y a, par exemple, deux lemmes dans une mme sous-section, ils sont numrots : lemme 1 et lemme 2. Cela conduit un systme de rfrences internes tout fait explicite qu'il est inutile de dtailler davantage. Prcisons simplement que les rfrences internes un chapitre ne comportent pas l'indication de celui-ci.

Les sections sont, en gnral, divises par des intertitres qui concernent plusieurs sous-sections. Ces intertitres se retrouvent dans la table des matires mais ne font pas partie du systme de rfrences.

Le dbut et la fin des dmonstrations sont respectivement signals par les signes ~et t;;l.

A la fin de chaque chapitre figure une liste d'noncs d'exercices. Les solutions sont regroupes la fin du tome correspondant. Dans les solutions d'exercices, les rfrences sont traites comme dans le chapitre correspondant : celles qui ne comportent pas d'indication de chapitre sont internes ; ainsi, la mention dcoule du corollaire 2.4 que l'on trouve dans le corrig de l'exercice 21 du chapitre 5 se rapporte au corollaire 2.4 du chapitre 5. Les solutions sont, surtout pour les premiers chapitres, assez dtailles.

Notre lecteur est suppos avoir une certaine pratique des mathmatiques, et des connaissances correspondant, grosso modo, aux mathmatiques classiques enseignes dans les lyces et dans les premiers cycles universitaires. Nous nous rfrerons librement ce que nous avons appel ce fonds commun, en particulier dans les exemples et les exercices.

Cependant, le cours lui-mme ne suppose dans l'ensemble aucune connaissance particulire pralable.

4 Mode d'emploi

Nous utilisons la terminologie et les notations les plus rpandues pour tout ce qui relve du (mta-)langage mathmatique ensembliste habituel : oprations sur les ensembles, relations, applications, etc, de mme que pour les ensembles les plus frquents en mathmatiques : IN, 71., 71. f n71., Q, IR.

Si E et F sont des ensembles, et si f est une application dfinie sur une partie de E et valeurs dans F, le domaine de fest not dom(f) (c'est l'ensemble des lments de E en lesquels fest dfinie), et son image est note lm(f) (c'est l'ensemble des lments y appartenant F tels que, pour au moins un lment x de E, on ait y= f(x)). Si A est une partie du domaine de f, la restriction de f A est l'application de A dans F, note ft A, qui, chaque lment x de A, associe f(x). L'image de l'application ft A est aussi appele image directe de A par f et note f[A]. Si B est une partie de F, l'image rciproque de B par fest la partie de E, note f-1[8], constitue des lments x de E tels que f(x) E B. En fait, tant donne une application f d'un ensemble E dans un ensemble F, on peut lui associer canoniquement une application de ~(E) (ensemble des parties de E) dans ~(F) : l'application image directe, note f, qui, toute partie A de E, associe f[A], qu'on pourra donc galement noter f(A). On peut de mme associer f une application de ~(F) dans ~(E), l'application image rciproque , note f-1, qui, toute partie B de F, associe f-1[8], qu'on notera donc aussi f-1(8). (Voir aussi l'exercice 19 du chapitre 2.)

Il est peut-tre galement utile de donner quelques prcisions sur la notion de mot sur un alphabet, qui sera la premire utilise :

Soit E un ensemble, fini ou infini, que nous appelons alphabet. Un mot rn sur l'alphabet E est une suite finie d'lments de E (c'est--dire une application de l'ensemble { 0,1, ... ,n -1} (n tant un entier) dans E) ; on crira rn= (ao,ah ... ,an-1) ou mme aoa1 ... an-l le mot qui est l'application de domaine { 0,1, ... ,n -1} qui i (0 ~ i ~ n- 1) fait correspondre ai L'entier n est appel la longueur du mot rn et est note lg[m]. L'ensemble des mots sur E est not vlt'(E).

Si n = 0, on obtient le mot vide. On fera l'abus de langage consistant identifier un mot (a) de longueur 1 avec l'lment a. L'ensemble vlt{E) peut tre muni d'une opration binaire, la concatnation: soient m1 = (ao,ah ... ,an-1) et m2 = (bo,bh ... ,bm-1) deux mots. On peut former le nouveau mot rn= (ao,ah,an-l,bo,bl,,bm-1) (c'est--dire l'application rn de { 0,1, ... ,n + rn -1} dfinie comme suit : si 0 ~ i ~ n -1, alors m(i) =ai; si n ~ i ~ n +rn -1, alors m(i) = bi-n) Ce mot est appel le concatn de m1 avec m2 et est not rn 1m2. Cette notation est justifie par le fait que la concatnation est une opration associative.

Etant donns deux mots rn et mh on dit que m1 est un segment initial de rn s'il existe un mot m2 tel que rn= m1m2. Autrement dit, si rn= (ao,al, ... ,an-1), les segments initiaux de rn sont les mots de la forme (a0,ah ... ,ap-1) o pest un entier infrieur ou gal n. On dit que m1 est un segment final de rn s'il existe un mot m2 tel que rn= m2m1 ; les segments finaux de (ao,ah,an-1) sont donc les mots de la forme (ap,ap-t1,, an-1) (p

Mode d'emploi 5

tant un entier infrieur ou gal n). En particulier, le mot vide et rn lui-mme sont des segments initiaux et des segments finaux de m. Un segment (initial ou final) de rn est propre s'il est diffrent de rn et du mot vide.

Lorsqu'un lment b de l'alphabet apparat dans un mot rn= aoa 1 ... an_1, on dit qu'il a une occurrence dans rn, et les divers endroits o il apparat s'appellent les occurrences de b dans m. On peut naturellement tre plus prcis et plus formel : on dira que b a une occurrence dans rn si b est gal l'un des ah pour i compris entre 0 et n -1 (c'est--dire si b appartient l'image de rn) ; une occurrence de b dans rn est un entier k, infrieur lg[m], tel que b =a k. Par exemple, la troisime occurrence de b dans rn est le troisime lment de l'ensemble { k ; 0 ~ k ~ n -1 et ak = b} rang dans l'ordre croissant. Ce formalisme ne sera pas explicitement utilis dans le cours : l'ide donne au dbut de ce paragraphe sera amplement suffisante pour ce que nous aurons faire.

Les faits suivants sont peu prs vidents et seront constamment utiliss :

pour tous mots m1 et m2, lg[m1m2] = lg[m1] + lg[m2] ; pour tous mots m1, m2 et m3, l'galit m1m2 = m1m3 implique l'galit m2 = m3

(on dit que l'on peut simplifier gauche) ; pour tous mots mh m2 et m3, l'galit mtm2 = m3m2 implique l'galit mt= m3

(on peut simplifier droite) ; pour tous mots mt, m2, m3 et m4, si mtm2 = m3m 4, alors mt est un segment

initial de m3 ou m3 est un segment initiai de mt. D'une faon analogue, avec les mmes hypothses, m2 est un segment final de m4 ou m4 est un segment final de m2 ;

si mt est un segment initial de m2 et m2 est un segment initial de mt, alors mt=m2.

On utilisera aussi le fait que vK(E) est dnombrable si E est fini ou dnombrable (c'est le thorme 4.9 du chapitre 7).

Chapitre 5

Rcursivit

8 Chapitre 5. Rcursivit

Les fonctions rcursives sont des fonctions de INP (une puissance cartsienne de l'ensemble des entiers naturels) dans IN. Intuitivement, ce sont les fonctions qui sont effectivement calculables, ou, si l'on prfre, pour lesquelles il existe un algorithme de calcul, ou encore qui peuvent tre calcules par une machine. Il faut noter que c'est seulement la possibilit thorique d'un calcul mcanique qui est considre ici, le calcul d'une fonction pouvant trs bien prendre un temps beaucoup trop long pour que l'on puisse raisonnablement l'envisager.

Dans une premire section, on dfinit une classe de fonctions, les fonctions rcursives primitives, qui rpondent manifestement au critre du paragraphe prcdent. On essaiera de convaincre le lecteur que cette classe est dj fort riche en montrant que toutes les fonctions qui viennent l'esprit sont rcursives primitives. Malheureusement, les fonctions rcursives primitives n'puisent pas la classe que nous voulons dcrire: dans la seconde section, on construira une fonction, la fonction d'Ackermann, qui n'est pas rcursive primitive bien qu'elle soit effectivement calculable. On dfinit donc une classe plus riche, la classe des fonctions rcursives. Mais en fait, il est ncessaire, pour des raisons qui apparatront aussi la quatrime section, de dfinir une classe plus complique et a priori moins naturelle, la classe des fonctions partielles rcursives. Une fonction partielle f p variables est une application d'un sous-ensemble E de INP dans IN et elle est rcursive s'il existe un algorithme qui la calcule dans le sens suivant : si on applique l'algorithme pour calculer f{n 11n2, ... ,np) et si {n 11 n2, ... ,np) E E, alors il effectuera le calcul; si (n 1,n 2, ... ,np) ~ E, alors l'algorithme ne s'arrtera jamais. Il semble bien que l'on ait cern la notion de fonction calculable: on n'a jamais pu trouver de fonction que l'on sache effectivement calculer et dont on ne sache dmontrer qu'elle est rcursive ou partielle rcursive.

Les machines de Turing, qui sont une version mathmatique des machines calculer ou des ordinateurs, sont dfinies dans la troisime section. On montre que les fonctions qu'elles calculent sont exactement les fonctions partielles rcursives. Il y a bien d'autres machines mathmatiques qui ont t dfinies, mais nous avons prfr les machines de Turing, car leur intrt est multiple: premirement historique, car ce sont les premiers modles de machines mathmatiques qui aient t introduits; ensuite pdagogique, car on voit comment la machine fonctionne de faon quasiment mcanique ; enfin thorique, car elles permettent de montrer les importants thormes d'numration et du point fixe. Ceci sera fait dans la quatrime section.

1. Fonctions et ensembles rcursifs primitifs 9

1. FONCTIONS ET ENSEMBLES RECURSIFS PRlMITIFS

Les premires dfinitions

1.1 On va dfinir l'ensemble des fonctions rcursives primitives par induction, par un procd analogue celui que nous avons utilis pour dfinir les formules du calcul propositionnel ou du calcul des prdicats : ce sera la plus petite classe de fonctions contenant certaines fonctions que l'on va spcifier et close pour certaines oprations. On a besoin de quelques justifications et notations avant de donner la dfinition.

Soit p un entier ; on dsignera par a-P l'ensemble des applications de !NP dans IN. On conviendra que, si p = 0, !NP ne contient que la suite vide et les lments de a-o peuvent alors tre identifis avec les lments de IN; on notera a-l'ensemble Ua-P.

pd~

Si i est un entier compris entre 1 et p, la i-me projection P ~ est la fonction de a-P dfinie par :

P~(x1 ,x2, ... ,xp) = Xj. On utilisera dans ce chapitre les notations suivantes, provenant du

lambda-calcul : avec ces notations, la fonction P ~ s'crit : p~ = X1X2Xp.Xj.

D'une faon gnrale, ..h1x2 ... xp.t, o t est une expression faisant intervenir les variables x1,x2, ... xp, dsigne la fonction qui n1,n2, ... ,np fait correspondre t(n 11 n2, ... ,np). Cette notation peut aussi tre utilise pour des fonctions de !NP dans INq : par exemple .hy.(x + y,3x + 2y) est la fonction de IN2 dans lui-mme qui au couple (m,n) fait correspondre le couple (rn+ n,3m + 2n).

Par dfinition, la fonction successeur S est la fonction X.x+ 1, c'est--dire la fonction de a-1 qui chaque entier n fait correspondre n+ 1.

Si f1, f2, ... ,fn appartiennent a-P et g appartient a-n, la fonction compose h = g(f1,f2, ... ,fn) est l'lment de a-P gal

X1x2 ... xp.g(f1(x1,x2, ... ,xp), f2(x1,x2, ... ,xp ), ... , f n (x1,x2, ... ,xp) ).

1.2 Dfinition par rcurrence: C'est un procd de dfinition de fonctions qui est justifi par le fait vident suivant : soient g E a-P et h E a-p+2 ; alors il y a une et une seule fonction fE a-P+l qui, pour tous x1,x2, ... ,xp et y de IN, vrifie les conditions suivantes :

i) f(xl,x2, ... ,xp,O) = g(xhx2, ... ,xp) ; ii) f(xl,x2, ... ,xp,y+1) = h(x1,x2, ... ,xp,y,f(x1,x2, ... ,xp,y)).


On dit que f est la fonction dfinie par rcurrence partir de g (condition initiale) et h (tape de rcurrence).

REMARQUE : il faut se convaincre que la dfinition par rcurrence permet le calcul effectif de la fonction dfinie. Plus prcisment, supposons que g et h sont deux fonctions comme ci-dessus et que, de plus, on sache les calculer effectivement l'aide d'algorithmes .A1 et .A2 respectivement. Alors, il n'est pas difficile d'imaginer un autre algorithme qui calcule la fonction f dfinie par rcurrence partir de g et h : pour calculer f(n 1,n 2, ... ,np,m), il faut d'abord calculer f(n 11n2, ... ,np,O) (qui est gal g(n 1,n2, ... ,np) ; on utilise l'algorithme .A1), puis f(n 1,n 2, ... ,np,1) (en utilisant la dfinition de f et l'algorithme .A2) et on continue jusqu' obtenir la valeur voulue.

1.3 DEFINITION : L'ensemble des fonctions rcursives primitives est le plus petit des sous-ensembles E de~ satisfaisant les conditions suivantes :

i) E contient toutes les fonctions constantes de !NP dans IN pour tout entier p.

ii) E contient toutes les projections PJ pour tous entiers p et i tels que 1 ~ i ~ p.

iii) E contient la fonction successeur S. iv) E est clos par composition, ce qui veut dire que, si n et p sont

des entiers, si f1,f2, ,fn sont des fonctions de ~P qui appartiennent E, et si gE ~n est aussi dans E, alors la fonction compose g(f11f2 , ... ,fn) appartient E.

v) E est clos par rcurrence, ce qui veut dire que, si p est un entier, sig appartenant ~P et h appartenant ~p .. 2 sont toutes les deux dans E, alors la fonction f dfinie par rcurrence partir de g et h est aussi dansE.

REMARQUE : Comme on l'a fait pour l'ensemble des formules du calcul propositionnel ou du calcul des prdicats, on aurait pu donner une dfinition par le bas de l'ensemble des fonctions rcursives primitives. On pose : R0 = {'Y ; p E IN et 'Y est une fonction constante de !NP dans IN} U { P J ; 1 ~ i ~ p} u { S }, et, pour tout entier n :

Rn+l =Rn U { h ; h est obtenue par rcurrence partir de deux fonctions de Rn} u { h ; h est obtenue par composition partir de fonctions de de Rn } ;

alors l'ensemble des fonctions rcursives primitives est gal U Rn. nt.IN


Pour montrer qu'une fonction est rcursive primitive, il suffit montrer comment l'obtenir, l'aide des clauses iv) et v) et partir des fonctions dcrites eni), ii), iii), ou plus gnralement partir de fonctions dont on sait dj qu'elles sont rcursives primitives. On verra des exemples trs bientt.

D'autre part, pour montrer que toutes les fonctions rcursives primitives possdent une certaine proprit .9, il suffit de montrer que les fonctions mentionnes aux alinas i), ii) et iii) ont cette proprit et que la classe des fonctions satisfaisant .9 est close par composition et par rcurrence.

On peut voir aussi que, pour toute fonction f rcursive primitive, il existe un algorithme la calculant : c'est vrai pour les fonctions de Ro et, si c'est vrai pour les fonctions de Rn, a l'est aussi pour celles de Rn+t

1.4 DEFINITION : On dit qu'un ensemble A INP est rcursif primitif si sa fonction caractristique est rcursive primitive.

Rappelons que la fonction caractristique XA de l'ensemble A est dfinie par : XA(nt,n2, ... ,np)= 1 si (n 1,n2, ... ,np) E A ; XA(n.,n2, ... ,np)= 0 sinon.

La fonction caractristique de l'ensemble A sera note XA ou x(A) suivant les exigences de la typographie. Si .9(x1,x2, ... ,xp) est une proprit portant sur les entiers x1,x2, . ,xp (on parlera aussi de prdicat d'arit p), on dira que .:; est rcursive primitive si l'ensemble

est rcursif primitif.

Exemples et propritffi de clture 1.5 L'addition )..xy.x +y est rcursive primitive: en effet, elle peut se dfinir par rcurrence par :

x+ 0 =x; x+ (y+ 1) =(x+ y) + 1.

Soyons pour cet exemple (mais pour celui-ci seulement) d'une prcision maniaque. Notons ad la fonction addition (ad= >.xy.x +y). Alors

ad(x,O)=P~(x) ; ad(x,y + 1) = S(P~(x,y,ad(x,y))).


La multiplication est aussi rcursive primitive. On peut la dfinir par rcurrence partir de l'addition:

xO=O; x. (y + 1) = x. y + x.

La fonction >.xy.xY est aussi rcursive primitive. Elle peut se dfinir par : x0 = 1; xY+l =xYx.

Convenons de noter x .:.1 l'entier gal x - 1 si x > 0 et 0 sinon. Alors la fonction .;\x.x .:.1 est rcursive primitive. En effet elle peut tre dfinie par rcurrence par:

o.:.1 =O; (x+ 1).:.1 =x.

Plus gnralement, notons x =-y l'entier gal x- y si x~ y et 0 sinon. La fonction .;\xy.x.:. y est elle aussi rcursive primitive :

x.:.O=x; x.:.(y+ 1)=(x.:.y) =-1.

Dfinissons la fonction sg par : sg(O) = 0 et sg(x) = 1 si x =t:O. La fonction sg est rcursive primitive : en effet sg(x) = 1.:. (1.:. x).

Le prdicat x> y est rcursif primitif (ce qui veut dire que l'ensemble {(x, y) ; x > y} est rcursif primitif). En effet, la fonction caractristique de cet ensemble est gale sg(x =-y). De mme le prdicat x~ y, dont la fonction caractristique est sg((x + 1).:.y), est rcursif primitif.

1.6 Nous allons maintenant montrer que les fonctions rcursives primitives et les prdicats rcursifs primitifs jouissent d'un certain nombre de proprits de clture.

L'ensemble des fonctions rcursives primitives est clos par substitution de variables : si fE a-P est rcursive primitive et si u est une application de l'ensemble { 1,2, ... ,p} dans lui-mme, alors la fonction X1x2 ... xp.f(Xau> ,Xa , ... ,xa) est aussi rcursive primitive. En effet, cette fonction est gale f(P~ ,P~ , ... ,P~ ).

Si A IN" est rcursif primitif et si f11f2, ... ,fn appartiennent a-P et sont rcursives primitives, alors l'ensemble

{ (x11x2, ... ,xp) ; (f1(x1,x2, ... ,xp),f2(x11x2,,xP), ... ,fn(x1,x2, ... ,xp)) E A} est aussi rcursif primitif (sa fonction caractristique est XA(fhf2, ... ,fn)

On dduit facilement de ce qui prcde que, si f et g sont deux fonctions rcursives primitives de a-p, alors les ensembles

{ (x11x2, ... ,xp) ; f(x1,x2, ... ,xp) > g(x1,x2,,xp)} , { (x1,x2, ... ,xp) ; f(x1,x2, ... ,xp) = g(x1,x2, ... ,xp)}

et { (x11x2, ... ,xp) ; f(x1,x2,. .. ,xp) < g(x1,x2, ... ,xp)} sont rcursifs primitifs. En particulier, l'ensemble { (x1,x2, ... ,xp) ; f(x1,x2, ... ,xp) > 0} est rcursif primitif.


Pour chaque entier p, l'ensemble des sous-ensembles rcursifs primitifs de INP est clos pour les oprations boolennes : si A et B sont des sous-ensembles rcursifs primitifs de INP, il en est de mme de An B, AU B et INP- A. On peut en effet calculer les fonctions caractristiques de ces nouveaux ensembles :

x( An B) = x(A).x(B); x( Au B) = sg(x(A) + x(B)) ; x(INP- A)= 1.: x(A).

Remarquons en particulier que A - B =An (INP - B) est rcursif primitif.

1.7 Schma de dfinition par cas: soient f et g deux fonctions rcursives primitives de a-P et A un sous-ensemble rcursif primitif de INP ; alors la fonction h dfinie par :

h(x11x2, ... ,xp) = f(xhx2, ... ,xp) si (xhx2, ... ,xp) E A , h(xt,x2, ... ,xp) = g(xhx2, ... ,xp) sinon,

est rcursive primitive. Il suffit de remarquer que h = f.x(A) + g.x(INP.: A). On peut gnraliser cette possibilit de dfinition par cru; : soient ft,f2, ... ,fn+t E a-P

des fonctions rcursives primitives et At,A2, ... ,An INP des ensembles rcursifs primitifs ; alors la fonction g dfinie par : g(xhx2, ... ,xp) = ft(xhx2, ... ,xp) g(xt,X2,,xp) = f2(xt,x2,,xp) g(x1,x2, ... ,xp) = f3(xt,x2, ... ,xp)

si (xt,x2, ... ,xp) E Ah si (x11x2, ... ,xp) ~At et (xt,x2, ... ,xp) E A2, si (xt,x2, ... ,xp) ~At U A2 et (x1,x2, ... ,xp) E A3,

g(xt,x2, ... ,xp) = fn+t(Xt,x2, ... ,xp) si (xt,x2, ... ,xp) ~At U A2U ... UAn, est une fonction rcursive primitive. En effet, on peut remarquer que : g=ftx(At) + f2x(A2-At) + f3x(AJ-(AtUA2)) + ..

+ fn x(An -(At U A2U ... UAn-t)) + fn+t' x(INP - (At U A2U ... UAn)).

En corollaire, on voit que les fonctions htx2 ... xp.sup(xhx2, ... ,xp) et htx2 ... xp.inf(xt,x2, ... ,xp) sont rcursives primitives. Par exemple, sup(xhx2, ... ,xp) peut tre dfinie de la faon suivante :

sup(xt,x2, ... ,xp) = Xt si Xt ~ x2 et Xt ~ XJ et ... et x1 ~ xp ; sup(xhx2, ... ,xp) = x2 sinon et si x2 ~ XJ et ... et x2 ~ xp, etc.

1.8 Somme et produit limits: soit f une fonction rcursive primitive de a-P+l Alors les fonctions

g = MtX2xpy.E~: f(xhx2, ... ,xp,t) et - t=y h- htx2xpy.nt=o f(xt,x2, ... ,xp,t) sont aussi rcursives primitives. Elles se dfinissent facilement par rcurrence. Pour la somme, par exemple :


g(xhx2, ... ,xp,O) = f{x1,x2, ... ,xp,O) ; g(xl,x2,,xp,y + 1) = g(x1,x2, ... ,xp,y) + f(xhx2, ... ,xp,y + 1).

En particulier, la fonction factorielle ..\x.x! , qui peut tre dfinie comme produit limit, est rcursive primitive.

1.9 Schma JI. born: soit A un sous-ensemble rcursif primitif de 1NP+1. Alors la fonction f de a-P+l dfinie comme suit est rcursive primitive :

f{x1,x2, ... ,xp,z) = 0 s'il n'existe pas d'entier t ~ z tel que {x1,x2, ... ,xp,t) EA ; sinon f{x1,x2, ... ,xp,z) est gal au plus petit des entiers t ~ z tels que

(xl,x2, ... ,xp,t) E A. La fonction f est dfinie par rcurrence, schma de dfini ti on par cas et somme

limite : f{xl,x2, ... ,xp,O) = 0; f{x1,x2, ... ,xp,z + 1) =f{xl,x2,,xp,z) si E~~~XA(x1 ,x2, ... ,xp,y) ~ 1; f{x1,x2, ... ,xp,z + 1) = z + 1 sinon et si {x1,x2, ... ,xp,z + 1) E A ; f{x1,x2, ... ,xp,z + 1) = 0 dans les autres cas.

Pour dsigner cette fonction on utilisera la notation suivante : f{x1,x2, ... ,xp,z) = p.t ~ z ({x11x2, ... ,xp,t) E A).

(lire : f{xhx2, ... ,xp,z) est le plus petit des entiers t infrieurs ou gaux z tels que {xl,x2,,xp,t) E A.)

Dans l'utilisation de ce schma, la condition (xhx2, ... ,xp,t) E A aura souvent la forme g(xhx2, ... ,xp,t) = 0 , o g est une fonction rcursive primitive.

L'ensemble des prdicats rcursifs primitifs est clos par quantification borne. Cela veut dire que, si A INP+l est rcursif primitif, il en est de mme des ensembles :

B = { (x1,x2, ... ,xp,z) ; 3t ~ z (x1,x2, ... ,xp,t) E A} et C = { (x1,x2, ... ,xp,z); Vt ~ z (x1,x2, ... ,xp,t) E A}. En effet la fonction caractristique de B est donne par la formule :

Xo(xhx2, ... ,xp,z) = sg(E~~~XA(xl,x2,,xp,t)), et celle de C par :

1.10 Profitons de ces connaissances toutes neuves pour montrer qu'un certain nombre de fonctions et d'ensembles sont rcursifs primitifs :

IN est rcursif primitif : sa fonction caractristique est la fonction constante de a-1 gale 1 ;

l'ensemble des nombres pairs est aussi rcursif primitif: sa fonction caractristique X est dfinie par rcurrence par : x{O) = 1 et x{n + 1) = 1.: x(n) ;

la fonction q(x,y) qui est gale la partie entire de x/y si y n'est pas nul et 0 si y est nul, est rcursive primitive ; elle est dfinie par :


q(x,y) = J,Lt ~x ((t + 1).y >x) ; l'ensemble { (x,y) ; y divise x} est rcursif primitif: sa fonction caractristique

est gale 1.:sg(x.:y.q(x,y)); 1 'ensemble {x ; x est un nombre premier} est rcursif primitif : en effet x est

premier si est seulement si x> 1 et Vy ~ x(y ~ 1 ou y= x ou y ne divise pas x) ; la fonction ~qui l'entier n fait correspondre le (n + 1)-me nombre premier

est rcursive primitive: elle est dfinie par rcurrence, grce au schma IJ. born, de la faon suivante :

~0) =2; ~n + 1) = J.LZ ~ (~n)! + 1)(z > ~n) et z est premier).

(On utilise ici le fait bien connu qu'il y a toujours un nombre premier strictement compris entre p et p! + 2.)

On trouvera dans les exercices d'autres exemples de fonctions et d'ensembles rcursifs primitifs.

Codages des suites

1.11 La notion de calculabilit ne s'applique pas seulement aux fonctions d'entiers dans les entiers. La gnralisation la plus simple et la plus utile consiste considrer des fonctions qui, chaque suite finie d'entiers, font correspondre un entier ou mme une autre suite finie. Pour pouvoir utiliser la thorie des fonctions rcursives dans ce contexte, on va coder les suites finies d'entiers. Ce que l'on va faire exactement, c'est tablir une application de l'ensemble des suites finies d'entiers valeurs dans les entiers. Il faut videmment que le codage que l'on utilise soit effectif, c'est--dire que l'on sache calculer l'entier correspondant une suite donne, et que, inversement, on puisse retrouver une suite partir de son code. Il y a bien des faons de faire cela. On va donner ici deux codages dont on se servira par la suite.

PROPOSITION : Pour chaque entier non nul p, il existe des fonctions rcursives primitives ap E ~p, fJ ~' {J~, ... , {J~ E ~1 qui possdent la proprit suivante : ap est une bijection de !NP sur IN dont l'application rciproque est x. (fJ Mx),fJ~(x), ... ,{J~(x) ).

~ On va commencer par construire ~- Pour cela, on numrote les couples d'entiers en suivant le schma ci -dessous :


10 (4,0)

Plus prcisment, on numre les couples (x,y) en suivant les diagonales x+ y= constante. On commence par la diagonale x+ y= 0 (qui ne contient qu'un seul couple), puis on passe la diagonale x + y = 1 en commenant par le bas, etc. La valeur de a:z(x,y) est exactement le nombre de couples prcdant (x,y) dans cette numration. La diagonale x+ y= n a exactement n + 1 lments. Donc avant le couple (p + n,O) il y a 1 + 2 + + (n + p) =Hn + p)(n + p + 1) lments. Le couple (p,n) se trouve sur la mme diagonale que (p + n,O) et exactement n places aprs lui. Par consquent :

lr:l(p,n) = t(n + p + 1)(n + p) + n. On remarque que a:z est bien rcursive primitive et suprieure ou gale n et p.

Puisque lr:2 est bijective, on peut retrouver n et p partir de a:z(p,n) l'aide des fonctions suivantes :

fJ~(x) = J.LZ ~ x (3t ~ x lr:l(z,t) =x) et {J~(x) = J.LZ ~ x (3t ~ x a:z(t,z) =x), et nous voyons que les fonctions {J~ et {J~ sont rcursives primitives.

On peut alors dfinir OJ par OJ(x,y,z) = a:z(x,a:z(y,z)) et {J~ = {J~ , {J~ = {J~o {J~ , {J~ = {J~o PL et plus gnralement

ap+1(x1,x2, ... ,xp,xp+1) = ap(x11x2, ... xp_1,a:z(xp,xp+1)) ;

fJ~+1=fJ~, fJ~+1=fJ~ , .. , PC~~=PC-1 , PC+1=fJ~ofJC, pg:~=fJ~ofJC. Pour complter, on posera a1(x) =x et {J~(x) =x. (;;')

NOTATION : On notera r# l'ensemble des suites finies d'entiers ( r# = .Jt(IN) ).

1.12 Dans l'exercice 3, on montre comment utiliser ces fonctions pour tablir un codage de toutes les suites finies. En voici un autre, trs classique, dont on se servira par la suite.

1. Fonctions et ensembles rcursifs primitifs

DEFINITION DE !l ET jj: La. fonction !l est l'application de # dans IN dfinie comme suit :

!l((xo,xh,xp)) = W'{O)x0. w-{1)x1 ... W'(p )xP (rappelons que r est la. fonction qui l'entier n fait correspondre le (n + 1)-me nombre premier). On compltera. cette dfinition en dcidant que, si s est la. suite vide, !l(s) = 1.

La. fonction /j est la. fonction de a-2 dfinie comme suit : 6(i,x) = J.LZ ~ x (x n'est pas divisible par W'(i)z+l)

(6(i,x) est l'exposant de W'(i) dans la. dcomposition de x en facteurs premiers).

17

On remarque que la fonction /j est rcursive primitive. Il n'est pas difficile de voir aussi que l'image den (c'est--dire {x; il existe sE# tel que x=!l(s)}) est l'ensemble IN- {0}. On n'a pas l un codage parfait puisque n n'est pas injective (il est clair que si s,s' E rt/, !l(s) = !l(s') si et seulement si la plus longue des deux suites s ou s' est obtenue partir de l'autre en ajoutant des zros la fin). On pourrait, d'ailleurs, la rendre injective en ajoutant un chaque exposant, mais on perdrait la surjectivit. D'autre part, n prend trs rapidement des valeurs normes, et est donc inutilisable pour des calculs autres que thoriques. Mais cela n'a pas d'importance pour l'usage que l'on veut en faire.

1.13 EXEMPLE : Les rcurrenB doublE~J. Soient g, g' E a-P et h, h' E a-p+J, quatre fonctions. A l'aide de ces fonctions, on peut dfinir simultanment deux nouvelles fonctions f et f' de a-P+l par les conditions :

f(x1,x2, ... ,xp,O) = g(x1,x2, ... ,xp) ; f'(x1,x2, ... ,xp,O) = g'(x1,x2, ... ,xp) ; f(x1,x2, ... ,xp,y + 1) = h(x1,x2, ... ,xp,y,f(x1,x2, ... ,xp,y),f'(x1,x2, ... ,xp,y)); f'(x1,x2, ... ,xp,y + 1) = h'(x1,x2, ... ,xp,y,f(xhx2, ... ,xp,y),f'(xhx2, ... ,xp,y)).

Nous allons voir que, si g,g',h,h' sont toutes les quatre rcursives primitives, il en est de mme de f et f'. Pour cela, introduisons la fonction k = ~(f,f'). Cette fonction peut tre dfinie par rcurrence de la faon suivante :

k(x1,x2, ... ,xp,O) = ~(g(x11x2, ... ,xp),g'(xhx2, ... ,xp)) ; k(x1,x2, ... ,xp,y + 1) = ~(h(xhx2, ... ,xp,y,{J~(k(x1 ,x2, ... ,xp,y)),{J~(k(x1 ,x2, ... ,xp,y))),

h '(xhx2, .. ,xp,y ,{J~(k(x1,x2, ... ,xp,y) ),{J~(k(x1 ,x2, ... ,xp,y))) ). La fonction k est donc rcursive primitive et f = P~ok et f' = {J~ok le sont aussi.


2. FONCTIONS RECURSIVES

La fonction d 'Ackermann

2.1 Il s'agit dans cette sous-section de donner un exemple de fonction calculable au sens intuitif du terme, qui n'est pas rcursive primitive, ce qui justifiera le travail supplmentaire demand au lecteur dans la suite. La fonction que nous allons dfinir et que nous appellerons la fonction d' Ackermann, bien que ce soit une lgre variante de la fonction originellement dfinie par Ackermann, est une fonction deux variables que nous noterons { et qui est dfinie comme suit :

i) pour tout entier x, {(O,x) = 2x; ii) pour tout entier y, {(y,O) = 1 ; iii) pour tous entiers x et y, {(y+ 1,x + 1) = {(y,{(y + 1,x)).

Pour chaque entier n, appelons {n la fonction ..\x.{(n,x). Alors {0(x) = 2x, et on voit facilement, partir de la clause iii) ci-dessus, que, pour tout n positif, {n est dfinie par rcurrence partir de {n-l par

{n(O) = 1 et {n(x + 1) = {n-l({n(x)). Cela montre d'abord qu'il y a une seule fonction {satisfaisant les conditions imposes, et de plus, que toutes les fonctions {n sont rcursives primitives (faire une rcurrence sur n). En revanche, rien ne nous permet d'affirmer que la fonction { elle-mme l'est, et c'est heureux car on va montrer qu'elle ne l'est pas. Pourtant, on peut effectivement calculer {(x,y) pour n'importe quelles valeurs de x et y, comme le lecteur peut s'en convaincre facilement. Il nous faut maintenant montrer quelques lemmes faciles mais ennuyeux concernant cette fonction f

2.2 LEMME 1 : Pour tout n et pour tout x, {n(x) >x.

~ On va utiliser un raisonnement faisant intervenir deux rcurrences embotes : par rcurrence sur n, on montre que, pour tout x, {n(x) >x. C'est clair pour n =O. Fixons n > 0 et supposons 1' assertion

pour tout entier x, {n-1(x) > x vraie. On montre alors l'assertion

pour tout entier x, {n(x) >x. Pour cela, on fait maintenant une rcurrence sur x. C'est clair pour x= 0 puisque {n(O) = 1. On suppose donc {n(x) >x et on va montrer {n(x + 1) >x+ 1. On sait que

2. Fonctions rcursives

{n(x + 1)={n-1({n(x)), et donc, par la premire hypothse de rcurrence, on voit que: {n(x + 1) > {n(x) soit {n(x + 1) ~ {n(x) + 1.

Or, d'aprs la seconde hypothse de rcurrence, {n(x) >x. Le lemme en dcoule. ~

LEMME 2: Pour tout entier n, la fonction {n est strictement croissante.

19

~ C'est clair pour n gal O. Ensuite, cela dcoule immdiatement du lemme 1 et de la formule {n(x + 1) = {n-1({n(x)).

~

LEMME 3 : Pour tout n ~ 1 et pour tout x, {n(x) ~ {n-1{x).

~ C'est clair pour x= O. Pour x+ 1, puisque {n(x) ~x+ 1 et que {n-1 est croissante, {n-1{{n(x)) ~ {n-1{x + 1), et il suffit d'appliquer la formule

{n(x + 1) = {n-1{{n{x)).

Si k est un entier' notons e~ la fonction {n itre k fois (c'est--dire eR = ,\x.x, {~ = {n, et {~+ 1 ={no{~). Le lemme suivant est une collection d'vidences :

LEMME 4: Les fonctions {~ sont toutes strictement croissantes. De plus, pour tous rn, n, k, h et x, {~(x) < e~+1 (x) et {~(x) ~ x, {~o{~ = e~+h et, si rn ~ n, {~(x) ~ {~(x).

2.3 Donnons maintenant une dfinition :

DEFINITION : Soient fE a-1 et gE a-P. On dit que f domine g s'il existe un entier A tel que pour tout (xhx2, ... ,xp), g(xhx2, ... ,xp) ~ f{sup(xhx2, ... ,xp,A)).

En particulier, lorsque fest strictement croissante, f domine g si et seulement si g(xhx2, ... ,xp) ~ f{sup(xhx2, ... ,xp)) sauf pour un nombre fini de p-uples {x1,x2, ... ,xp).


Appelons Cn l'ensemble des fonctions qui sont domines par au moins une itre de {n:

Cn = { g ; il existe k tel que {~ domine g }. Il est bien clair que les fonctions suivantes appartiennent C0 : les fonctions

projections P J, les fonctions constantes, la fonction successeur S, la fonction h 1x2 ... xp.sup(x1,x2, ... ,xp), la fonction hy.x +y et les fonctions ..h.kx o k est un entier quelconque. De plus, la fonction {n appartient Cn. D'autre part, si f et g appartiennent toutes deux iJp, si g E Cn et si pour tous x1,x2, ... ,xp, f{x1,x2, ... ,xp) ~ g{x1,x2, ... ,xp), alors fE Cn. Nous allons montrer :

LEMME 5: Pour tout entier n, l'ensemble Cn est clos par composition.

~ Soient f1,f2, ... ,fm des fonctions p variables de Cn et g une fonction rn variables de Cn. Il s'agit de montrer que g{f1,f2, ... ,fm) est aussi dans Cn. On sait qu'il existe des entiers A,Al,A2, ... ,Am,k,khk2,,km tels que, pour tous Y11 Y2, ... , Ym,

g(Y1lY2,,Ym) ~ {~(sup(yl,Y2,,Ym,A)), et pour tous x1, x2, . , Xp et pour tout i compris entre 1 et rn,

f(xhx2,,xp) ~ {~i(sup(xl,x2,,xp,A)}. Posons B = sup{A,A1,A2, ... ,Am) et h = sup(k11k2, ... ,km) En utilisant le lemme 4, on voit alors que, pour tous x1,x2, ... ,xp :

g{f1{x1,x2, ... ,xp),f2{x1,x2, ... ,xp), ... ,fm{x1,x2, .. ,xp)) ~ {~( {~{sup(x1,x2, ... ,xp,B)) ), et donc

LEMME 6: Pour tous entiers n, k et x, {~(x) ~ {n+l(x + k).

~ Par rcurrence sur k ; pour k gal 0 ou 1, c'est clair. Si c'est vrai pour k, a l'est pour k + 1 :

e~1 (x) = {n({~(x)) ~ {n({n+l(x + k)) = {n+l(x + k + 1) (l'ingalit dcoule de l'hypothse de rcurrence, la dernire galit de la dfinition de {).

~


LEMME 7: Soient gE 3'p et h E 3'p+2 et on suppose de plus que h et g sont toutes deux dans Cn {n ~ 0). Alors la fonction f dfinie par rcurrence partir de g et h appartient Cn+t

~ Traduisons les hypothses. Tout d'abord la dfinition de f: f{xt,x2,,xp,O) = g(xt,x2,,xp) ; f{Xt,X2, ... ,Xp,y + 1) = h{Xt,X2,,Xp,y,f{x1,x2, ... ,Xp,y)) ;

21

ensuite les conditions de domination : il existe A11 A2, k11 k2 tels que, pour tous

g(x11x2, ... ,xp) ~ ~~ 1 (sup(Xt,X2, ... ,Xp,At)) ; h{xt,X2, ... ,xp,y,z) ~ ~~2(sup{xt,x2, ... ,xp,y,z,A2)).

On va maintenant montrer par rcurrence sur y que, pour tous Xt,x2, ... ,xp,y : ( *) f(xt,X2,,Xp,y) ~ ~~t+yk2(sup(xt,X2,,Xp,y,At,A2)}.

C'est clair pour y= 0; si c'est vrai pour y, a l'est pour y+ 1 : f(xt,X2, ... ,xp,y + 1) = h(xt,x2, ... ,xp,y,f(xt,X2,,xp,y)) ; f(xt,X2, ... ,xp,y + 1) ~ ~~2(sup(x1 ,x2, ... ,xp,y,f(x11x2,,xp,y),A2)).

Donc, en utilisant l'hypothse de rcurrence ( *) et le lemme 4, f(xt,x2, ... ,xp,y + 1) ~ ~~2(~~1+yk2(sup(xt,x2,,xp,y,At,A2))),

ce qui dmontre notre assertion ; maintenant, en utilisant le lemme 6, on obtient f(xt,X2,,Xp,y) ~ ~n+t(Sup(xt,X2,,xp,y,At,A2) + kt + k2Y)

Or la fonction Xtx2 ... XpY~n+t(sup(x1 ,x2,,xp,y,At,A2) + kt + k2Y) s'obtient par composition partir de fonctions de Cn+t ; elle est donc elle-mme dans Cn+t, de mme que f. (:,;)

Nous sommes maintenant en mesure d'noncer:

2.4 COROLLAIRE : L'ensemble U Cn contient toutes les fonctions rcursives n~N

primitives.

~ En effet, d'une part cet ensemble contient les fonctions constantes, les fonctions projections et la fonction successeur ; d'autre part, il est clos par composition et pour les dfinitions par rcurrence. f,;)

On en arrive au thorme principal de cette section :


THEOREME: La fonction d'Ackermann n'est pas rcursive primitive.

~ Raisonnons par l'absurde et supposons la fonction d'Ackermann rcursive primitive ; il en est de mme de la fonction ..h.e(x,2x). Il existe donc des entiers n,k, et A tels que, pour tout x > A, e(x,2x) ~ e~(x). Donc pour tout x > A, on a :

e(x,2x) ~ e~(x) ~ en+l(x + k) (lemme 6), et, si x> sup(A,k,n + 1), en+l(x + k)< en+1(2x) < ex(2x) = e(x,2x) (lemme 4), ce qui est absurde. (;;)

En fait, on peut voir que la fonction ..h.e(x,x) domine toutes les fonctions rcursives primitives.

Le schma JL et les fonctions partielles rcursives

2.5 Il nous faut donc dfinir une classe plus large, que nous appellerons la classe des fonctions rcursives. On le fera en admettant un nouveau schma de dfinition, le schma 1-L (non born). L'ide est la suivante: soit A un sous-ensemble de INP+l ; alors la fonction fE jp que ce schma 1-L permet de dfinir est la fonction qui (x11x2, ,xp) fait correspondre le plus petit entier z tel que (x1,x2, ... ,xp,z) E A. On voit tout de suite la difficult: que se passe-t-il s'il n'existe pas d'entier z tel que (x1,x2, ... ,xp,z) E A? Il faut remarquer qu'il ne nous est pas possible de faire ce que l'on a fait pour le schma 1-L born et poser dans ce cas f(x1,x2, .. ,xp) =O. En effet, en admettant, ce que l'on doit faire, que l'on dispose d'un algorithme permettant de calculer la fonction caractristique XA de A, la seule faon imaginable de calculer f(x1,x2, ... ,xp) est de calculer XA(x1,x2,. .. ,xp,O), s'arrter si on trouve 1, sinon calculer XA(x11x2, ... ,xp,1), etc., jusqu' tomber sur la valeur 1. Mais si pour tout entier z, (x1,x2, .. ,xp,z)~A, alors le processus ne s'arrte pas, et on ne connatra jamais la valeur de f(x1,x2, ... ,xp) Autrement dit, on ne dispose pas d'algorithme pour calculer f, et on ne peut donc pas admettre ce schma. Une possibilit serait de le restreindre au cas o, pour tout (x1,x2,. .. ,xp), il existe z tel que (x11x2, .. ,xp,z) E A (on appellera ce schma le schma JL total). On obtiendrait, comme on le verra par la suite, toutes les fonctions rcursives. Mais il est prfrable de dfinir les fonctions rcursives partielles ; la raison en est que les thormes d'numration et de points fixes (thorme 3.18 et 4.14 de ce chapitre), essentiels dans cette matire, ne sont vrais que pour cette dernire classe (voir exercice 22).

2. Fonctions rcursives 23

Il s'agit donc de formaliser cette intuition ; pour commencer, donnons quelques dfinitions sur les fonctions partielles :

2.6 DEFINITION : Une fonction partielle de INP dans IN est un couple (A,f) o A INP et f est une application de A dans IN ; A est appel le domai.n de dfinition de la fonction.

NOTATION : On notera a: l'ensemble des fonctions partielles de INP dans IN, et i'=U a:.

pJ"O

Si (aha2, ... ,ap) t. A, on dira que la fonction n'est pas dfinie en (aha2, ... ,ap), ou encore que f(a 1,a 2, ... ,ap) n'est pas dfinie. On n'hsitera pas faire l'abus de langage consistant confondre (A,f) avec f. Il faut insister sur le fait que deux fonctions partielles f et g sont gales si, premirement, elles ont mme domaine de dfinition, et deuximement, elles sont identiques sur ce domaine. Si le domaine d'une fonction partielle f de a: est INP tout entier, on dit que f est totale. Le mot fonction restera rserv aux fonctions totales.

2.7 DEFINITION : Soient f1, f2, ... , fn E a: et gE~- La fonction compose h = g(fhf2, ... ,fn) est l'lment de a: dfini de la faon suivante:

h(xhx2, ... ,xp) n'est pas dfinie si l'une des fi(x1,x2, ... ,xp) n'est pas dfinie ou si, toutes l'tant, g(fl(xhx2, ... ,xp),f2(xhx2,,xp), ... ,fn(x1,x2,,xp)) n'est pas dfinie.

Dans le cas contraire, h(xhx2, ... ,xp) est dfinie et est gale : g(f1(x1,x2, ... ,xp),f2(x1,x2, ... ,xp), ... ,f n (x1,x2, ... ,xp) ).

REMARQUE : Il faut se mfier des automatismes lorsqu'on travaille avec les fonctions partielles. Prenons par exemple deux fonctions f et g de~ ; il n'est pas toujours vrai que f et (f + g) - g soient gales : si par exemple fest totale tandis que g n'est jamais dfinie, alors (f + g) - g n'est jamais dfinie. Et, effectivement, un algorithme qui essaierait de calculer (f + g) - g commencerait par calculer f + g et n'y parviendrait jamais.

2.8 Dfinition par rcurrence: On peut, pour les fonctions partielles, utiliser des dfinitions par rcurrence grce au fait suivant :


PROPOSITION : Soient g E ~ et h E ~+2 Alors, il existe une et une seule fonction fE ~+t vrifiant les conditions suivantes:

Pour tout (x,x2, ... ,xp) E INP, f(x1,x2, ... ,xp,O) = g(x11x2, ... ,xp) (ce qui veut dire exactement: f(x1,x2, ... ,xp,O) est dfinie si et seulement si g(x,x2, ... ,xp) l'est, et lui est gale dans ce cas).

Pour tout (x1,x2, ... ,xp,y) E INP+t, f(x1,x2, ... ,xp,y + 1) = h{x1,x2, ... ,xp,y,f(x,x2, ... ,xp,y))

(mme remarque que prcdemment: f(x1,x2, ... ,xp,y + 1) est dfinie si et seulement si h(x,x2, ... ,xp,y,f(x11x2, ... ,xp,y)) l'est).

On dira encore dans ce cas que f est dfinie par rcurrence partir de g et h.

2.9 DEFINITION : Le schma~- Soit fE ~+t Alors la fonction partielle g(xt,X2,,xp) = ~y(f(x11x2, ... ,xp,y) = 0)

est dfinie de la faon suivante : S'il existe au moins un entier z tel que f(x1,x2, ... ,xp,z) soit nul et

que, pour tout z' < z, f(x1,x2, ... ,xp,z') soit dfinie, alors g(x1,x2, ... ,xp) est le plus petit de ces entiers z.

Dans le cas contraire, g(x1,x2, ... ,xp) n'est pas dfinie. Si A INP+t, alors, par dfinition,

~y(xt,x2, ... ,xp,y) E A= ~y(1.:. XA(xt,x2, ... ,xp,y) = 0).

Il faut prendre garde ce que z = ~y(f(x.,x2, ... ,xp,y) = 0) implique que, pour tout y infrieur z, f(xhx2, .. o,Xp,y) est dfini (et non nul). Premirement, c'est la dfinition qu'il faut prendre si 1 'on veut suivre 1 'intuition de calculabilit effective (voir 3 0 9) ; deuximement, l'exercice 24 montre que ngliger cette prcaution conduirait des catastrophes 0

2.10 On peut maintenant dfinir l'ensemble des fonctions partielles rcursives :

DEFINITION : L'ensemble des fonctions partielles rcursives est le plus petit sous-ensemble de a* qui

contienne toutes les fonctions (totales) constantes, les projections P~ (pour 1 ~ i ~ p), la fonction successeurS,


soit clos pour la composition, les dfinitions par rcurrence et le schma J1. Un sous-ensemble A de INP est dit rcursif si sa fonction caractristique est (totale) rcursive.

25

On voit en particulier que les fonctions rcursives primitives sont rcursives (et mme totales rcursives). On vrifie aussi sans problme que les proprits de clture nonces en 1. 6, 1. 7, 1. 8 et 1. 9 pour les fonctions rcursives primitives sont encore vraies pour les fonctions partielles rcursives et les fonctions totales rcursives. On sait dj que la fonction d'Ackermann n'est pas rcursive primitive. Il faudra patienter jusqu' la fin de ce chapitre, ou faire l'exercice 11, pour voir qu'elle est rcursive, ce qui prouvera que la classe des fonctions rcursives est strictement plus riche que celle des fonctions rcursives primitives. Il est d'autre part ais de construire une fonction partielle rcursive qui n'est pas totale : par exemple la fonction partielle f(x) = JLy(2y =x) n'est dfinie que pour les nombres pairs. On donnera dans l'exercice 20 des exemples de fonctions rcursives dont le caractre partiel est beaucoup plus dfinitif: il en existe qu'il est impossible de prolonger en une fonction totale rcursive.

Le lecteur est invit se persuader que les fonctions partielles rcursives sont calculables dans le sens que nous avons mentionn dans l'introduction : pour chacune d'entre elles, il existe un algorithme qui, soit s'arrte au bout d'un temps fini en donnant la valeur de la fonction si celle-ci est dfinie au point considr, soit ne se termine jamais dans le cas contraire. La section suivante montrera comment calculer mcaniquement une fonction partielle rcursive.

2.11 Il reste le problme de la rciproque : une fonction calculable est-elle ncessaire-ment rcursive? Autrement dit, avons-nous russi dans notre tentative qui tait de for-maliser la notion de fonction calculable ? La rponse affirmative cette question est ce qu'on appelle la thse de Church. Il est clair que cette affirmation ne se prte pas dmonstration puisqu'on n'a pas de dfinition prcise de ce qu'est une fonction calcu-lable. D'autre part, l'chec de notre premire tentative, celle des fonctions rcursives primitives, doit nous rendre prudents. Mais en fait on ne connat aucun contre-exemple la thse de Church, et, de plus, l'exprience montre que, chaque fois que l'on a une fonction que l'intuition dit tre calculable, alors cette mme intuition permet de donner une preuve qu'elle est rcursive. En ce sens, les derniers thormes de ce chapitre (les thormes du point fixe) militent fortement en faveur de la thse de Church.


3. MACHINES DE TURING

3.1 Les machines de Turing sont des machines thoriques qui sont capables de calculer, en un sens que l'on dfinira, certaines fonctions de a;. Le fait important de cette section est qu'une fonction partielle est calculable par une machine de Turing si et seulement si elle est partielle rcursive.

Description des machines de Turing

Une machine de Turing se compose d'un nombre fini de bandes disposes horizontalement, toutes bornes gauche

et infinies droite ; chaque bande est divise en cases successives, les cases numro 1 tant les cases les plus gauche, suivies droite par les cases numro 2 etc. ; les bandes sont disposes de sorte que les cases d'un mme numro se trouvent sur une mme verticale.

case n"l case n"2 bande n"l case n"l case n"2 bande n"2 case n"l case n"2 bande n"3

l tte de lecture!

d'une tte que nous appellerons tte de lecture mais qui peut lire, crire ou effacer des symboles sur les bandes ( raison d'un symbole par case). La tte peut se dplacer horizontalement ; chaque instant, elle est pointe sur une verticale, c'est--dire sur la srie de cases d'un mme numro n correspondant aux diffrentes bandes et elle peut effectuer ces oprations (lecture, criture, effacement) sur toutes ces cases. Les symboles que la tte peut crire sont au nombre de trois : il y a le d qui est le symbole de dbut de bande, le bton 1 et le blanc b. On noteraS= { d, 1 ,b }.

Cela est commun toutes les machines de Turing. Maintenant, chaque machine est caractrise par la donne :

du nombre n de ses bandes.

3. Machines de Turing 27

d'un ensemble fini d'tats E ; chaque instant, la machine se trouvera dans un tat donn. Il y a deux tats particuliers qui appartiennent toutes les machines : 1 'tat initial ei et l'tat final er.

d'une table M qui est une application de 5" xE dans 5" xE x { -1,0,+ 1 }, quelquefois appele table de transition de la machine.

3.2 La machine fonctionne en changeant d'tat, en effaant et crivant sur les bandes et en dplaant sa tte chaque instant, en respectant les rgles suivantes :

l'instant t = 0, la tte se trouve devant les cases numro 1, sur lesquelles est crit le symbole d ; un symbole est crit sur chaque case de chaque bande. La machine se trouve dans l'tat initial ei ;

chaque instant t, la machine lit les symboles s11s2, ... ,sn inscrits sur les cases se trouvant devant sa tte ; la table M lui indique ce qu'elle doit faire : en supposant qu'elle se trouve dans l'tat e et que M(s1,s2, ... ,sn,e) = (sl,s~, ... ,s~,e',e) o t: E { -1,0,+1 }, alors la machine efface les symboles s1,s2, ... ,sn, crit sl,s~, ... ,s~ la place ; elle dplace sa tte d'une case vers la droite si t: = + 1, vers la gauche si t: = -1, et ne bouge pas sa tte si t: = 0 ; enfin elle passe dans l'tat e' ; l'instant t est alors coul et on passe l'instant t + 1 et la machine recommence les mmes oprations ;

lorsque la machine atteint l'tat final er, elle s'arrte de fonctionner.

Le bon fonctionnement de la machine exige que la table M satisfasse un certain nombre de contraintes :

la machine doit s'arrter de fonctionner aussitt atteint l'tat final ; cela se traduit par le fait que, pour tous s,s2, ... ,sn E 5", M(s,s2, ... ,sn,er) = (s11s2, ... ,sn,er,O) ;

il n'est pas possible la machine d'effacer ou d'crire le symbole de dbut de bande; d'autre part la tte ne peut aller gauche lorsqu'elle lit le symbole d. Donc, pour toute appartenant E, M(d,d, ... ,d,e) = (d,d, ... d,e',t:) o e' appartient E et t: est gal 0 ou +1 ; si (s11s2, ... ,sn) =F (d,d, ... ,d) et M(s11s2, ... ,sn,e) = (sl,s~, ... s~,e',e), alors aucun des si n'est gal d.

On fera toujours implicitement l'hypothse que ces conditions sont satisfaites. On supposera aussi que, l'instant t = 0, il n'y a qu'un nombre fini de cases remplies par autre chose que le blanc, et que le symbole d se trouve en dbut de chaque bande et uniquement l. Ces hypothses resteront vraies tout instant. On remarque aussi que le fonctionnement de la machine est compltement dtermin: on peut prvoir ce qui sera crit sur les bandes l'instant t si on sait ce qui y est crit l'instant initial t = 0

On va maintenant voir comment une machine de Turing peut calculer une fonction partielle, et montrer que les fonctions partielles qui sont ainsi calculables sont exactement les fonctions partielles rcursives.


Les fonctions T-calculables

3.3 Pour qu'une machine puisse calculer la valeur d'une fonction fen (x,x2, ... ,xp), il faut videmment rentrer les valeurs des variables {x1,x2, ... ,xp) d'une faon ou d'une autre. Cela se fera dans la configuration initiale. Pour calculer une fonction p variables, il faut une machine possdant au moins p + 1 bandes : sur les p premires bandes sont rentres les donnes, le rsultat est cod sur la (p + 1)-me bande, et les autres bandes (s'il y en a) servent aux calculs intermdiaires. Voyons d'abord comment coder un entier sur une bande :

DEFINITION : On dira qu'une bande reprsente, un instant donn, un entier x, si les symboles qui y sont crits cet instant sont :

{d,l' 1 ' ... ' l,b,b, ... ), x btons

c'est--dire le symbole d sur la premire case, le bton sur les cases numro 2,3, ... , x+ 1, puis des blancs sur les suivantes. Une bande o zro est reprsent (donc o il y a un d suivi de blancs) sera appele une bande blanche.

3.4 DEFINITION : Soient f une fonction partielle p variables et ~ une machine de Turing possdant au moins p + 1 bandes; on dit que ~ calcule f si, pour toute suite d'entiers (x,x2, ... ,xp), si l'on fait fonctionner la machine ~ partir d'une configuration initiale o, sur les bandes numro 1, 2, ... , p, sont respectivement reprsents les entiers x1, x2, ... , xp, les autres bandes tant blanches, alors:

si f{x,x2, ... ,xp) n'est pas dfinie, la machine ne s'arrte jamais (c'est--dire n'atteint jamais l'tat final) ;

si f{x,x2, ... ,xp) est dfinie, la machine s'arrtera au bout d'un temps fini, et, cet instant, x1 sera reprsent sur la premire bande, x2 sur la seconde, et ainsi de suite jusqu' la p-me et f(x,x2, ... ,xp) sur la (p + 1)-me bande. Les ventuelles autres bandes doivent tre blanches.

On dit que fE jp est T-calculable (T pour Turing) s'il existe une machine ~ ca.lculan t f.

REMARQUES : 1") On exige de la machine qu'elle nettoie ses bandes de calcul avant de s'arrter. Ce n'est pas vraiment ncessaire, mais cela aidera lorqu'on voudra faire


calculer une machine une fonction dfinie par rcurrence ou par composition. 2") Il existe bien d'autres dfinitions possibles de machines de Turing : certaines

n'ont qu'une seule bande, d'autres ont plus de symboles, etc. Elles sont toutes quivalentes en ce sens qu'elles calculent toutes exactement les mmes fonctions partielles. La notion qui est prsente ici a t choisie car, nous semble-t-il, elle permet une dmonstration pas trop complique du thorme fondamental de cette section, savoir que les fonctions partielles rcursives sont celles qui sont T-calculables, tout en minimisant les codages ncessaires.

3.5 Nous allons maintenant donner quelques exemples de fonctions T -calculables. A chaque fois, pour dcrire la machine correspondante, il faudrait prciser le nombre de bandes, les tats et la table. En fait, le plus souvent, seules les valeurs prises par la fonction M sur une partie de S x E sont utiles : certaines de ces valeurs sont imposes une fois pour toutes (voir 3.2) et d'autres ne vont jamais intervenir. On se bornera donc donner la partie utile de M.

EXEMPLE: La fonction successeur est T-calculable; on peut la calculer l'aide d'une machine deux bandes dont l'ensemble d'tats est { eher }. Voici la partie significative de sa table:

M(d,d,ei) = (d,d,e,+l); M( 1 ,b,ei) = ( 1,1 ,e,+l) ; M(b,b,ei) = (b, 1 ,er,O).

EXEMPLE : La fonction h.2x est T-calculable : la machine n'aura toujours que deux bandes ; il y a quatre tats, ei, er, e1 et e2 ; elle fonctionnera de la faon suivante : elle va lire la premire bande de gauche droite et chaque fois qu'elle lira un bton, elle en crira un sur la seconde bande et ira en crire un autre en fin de mot, toujours sur la seconde bande. Voici sa table:

M(d,d,ei) = (d,d,e,+l) (dmarrage) ; M ( l,b,ei) = ( 1, l,eh + 1) ; M(b,b,ei) = (b,b,er,O) (on rajoute un premier

bton sur la deuxime bande, sauf, bien sr, si x est gal 0) ; M( 1 ,b,e1) = ( 1 ,b,eh+l) ; M(b, 1 ,e1) = (b, 1 ,eh+l) (on va la fin du mot) ; M(b,b,e1) = (b, l,e2,-1); (on rajoute un bton) ; M(b, l,e2) = (b, l,e2,-1); M( l,b,e2) = (1 ,b,e2,-1) (on revient sous le

dernier bton que l'on a ddoubl) ; M(l,l,e2)=(l,l,ei,+l); M(b,l,ei)=(b,l,er,O) (on recommence jusqu'

avoir ddoubl tous les btons).

3.6 En fait, il n'tait pas indispensable de traiter l'exemple ci-dessus : on va maintenant montrer que, de faon gnrale, toutes les fonctions partielles rcursives sont


T -calculables. Pour cela, il faut montrer que les fonctions constantes, les projections et la fonction successeur sont T -calculables, et que 1 'ensemble des fonctions T -calculables est clos pour la composition, les dfinitions par rcurrence et le schma ~- Le cas de la fonction successeur est dj trait.

Commenons par la projection P~. Une machine qui calcule cette fonction peut tre facilement dcrite ; elle a p+ 1 bandes, deux tats e i et er et voici sa table M :

M{d,d, ... ,d,ei) = {d,d, ... ,d,e,+1); M{sl,s2,,sp,b,ei) = (shs2, ... ,sp, 1 ,ei,+1) si Si= 1 ;

si Si =b.

Les fonctions constantes sont aussi T -calculables ; dcrivons la machine calculant la fonction p variables constante gale k. Cette machine a p + 1 bandes et k + 2 tats ei,er,e1 ,e2 , ... ,ek ; sa table est donne par :

M{d,d, ... ,d,ei) = {d,d, ... ,d,e1,+ 1) ; M{s1,s2, ... ,sp,b,en) = (shs2,. .. ,sp, 1 ,en+h+1) pour tous s1,s2, ... ,sp et pour

tout n compris entre 1 et k-1 ; M{s1,s2, ... ,sp,b,ek) = (s11s2, ... ,sp, 1 ,er,O) pour tous s1,s2,. .. ,sp.

3.7 Il faut maintenant montrer que l'ensemble des fonctions partielles T-calculables est clos pour la composition, les dfinitions par rcurrence et le schma ~- Commenons par la composition : soient donc f1,f2, ... ,fn des fonctions de 3'; et gE~' et on suppose que toutes ces fonctions sont T-calculables. Il s'agit de construire une machine de Turing .At qui calcule la fonction partielle h =g{fhf2, ... ,fn) On sait que pour i compris entre 1 et n, il existe une machine .ti calculant fi ; on suppose que cette machine a Pi bandes (Pi ~ p + 1) et que son ensemble d'tats est Ei. Quitte renommer les lments des E i, on peut supposer que les ensembles E i sont deux deux disjoints (donc ont des tats initiaux et finaux diffrents). La fonction g est aussi calculable par une machine .;Y; cette machine a n'bandes, son ensemble d'tats est E; on supposera aussi que E est disjoint de tous les E i L'ensemble d'tats de la machine .At est E U ( V E i) ; son tat

1( 1(n initial est l'tat initial de .At1 et son tat final est l'tat final de .#'. Le nombre de bandes de .At est p' = p + E~~(Pi - p) + n'-n. On se contentera de dcrire le fonctionnement de cette machine .At calculant h, laissant au lecteur le soin d'tablir, s'il le dsire, sa table exacte.

On suppose donc qu' l'instant t = 0, les entiers x11x2, . ,xp sont reprsents sur les p premires bandes et que les autres bandes sont blanches. La machine commence calculer f1(x1,x2, . ,xp) en travaillant comme .At1, ceci prs qu'elle ne se sert pas de la bande numero p + 1. Elle utilise pour cela p1 des p' bandes qu'elle a sa disposition (les p premires et p1 - p autres) en ignorant les autres. Lorsqu'elle a fini son calcul (si jamais elle le finit), les entiers x11x2, ,xp restent represents sur les p premires bandes


et le rsultat f1(x17x2, ... ,xp) est reprsent sur une autre bande qe nous appellerons 81. L'tat final de la premire machine ramne la tte en dbut de bande, et lorsque celle-ci lit la suite de d, elle met .At dans l'tat initial de .A/2 En utilisant les p premires bandes plus p2 - p nouvelles bandes, elle va maintenant calculer f2(x17x2, ... ,xp) qui sera donc reprsent la fin du calcul (si fin il y a) sur une bande que nous appellerons 82 ; aprs quoi elle remettra sa tte en dbut de bande et calculera f3(x1,x2,. .. ,xp) et ainsi de suite. La seule chose laquelle il faille veiller est de ne pas se servir de la bande numro p + 1 pour y crire un des rsultats intermdiaires fi(x17x2, ... ,xp). Lorsque c'est termin et que la tte est revenue en dbut de bande, .At passe dans 1 'tat initial de .A", et travaille comme le ferait .A", en se servant de 81 (sur laquelle, rappelons-le est reprsent f1(x1,x2, ... ,xp)) comme premire bande, de 82 comme deuxime bande, etc., et en se servant de la bande numro p + 1 pour y crire le rsultat h(x1,x2, ... ,xp). Il ne reste plus qu' effacer le contenu des bandes 81, 82, etc.

3.8 Voyons maintenant comment calculer une fonction dfinie par rcurrence. Il s'agit donc de calculer la fonction partielle fE a:+1 dfinie par :

f(x1,x2, ... ,xp,O} = g(x1,x2, ... ,xp), f(x1,x2, ... ,xp,y + 1} = h(xhx2, ... ,xp,y,f(x,x2,,xp,y)},

o g E a: et h E a:+2 sont des fonctions partielles calcules par des machines .At et .At', respectivement. On supposera que les machines .At et .At 1 ont p + 1 + k et p + 3 + k' bandes, que leurs ensembles d'tats sont E et E' et que E et E' sont disjoints. L'tat final de .At est er, celui de .At 1 est eg. La machine .A" qui va calculer f est une machine p + 4 + k + k' bandes. L'ensemble de ses tats est EU E1 U { eo,e1,e2,e3,e_.,e5,e6,e7 } ( o les eh pour i variant de 0 7, sont de nouveaux tats n'appartenant pas dj E U E') ; son tat initial est 1 'tat initial de la machine .At . Il faut donc construire cette machine .A" de telle sorte que, si les entiers x1,x2, ... ,xp et Xp+1 sont reprsents sur les bandes numro 1, 2, p + 1 l'instant t = 0, l'entier f(x1,x2, ... ,xp,Xp+1) soit reprsent sur la bande p + 2 la fin du calcul. Voici comment elle fonctionne :

Pour commencer, elle va travailler comme .At, en utilisant les bandes 1,2, ... ,p,p + 4 ainsi que k bandes de calcul. A la fin de cette premire tape, il y a donc g(x1,x2, ... ,xp) reprsent sur la bande numro p + 4; ensuite, la tte est ramene en dbut de bande ; .A" passe alors dans l'tat e0.

La machine va alors calculer successivement f(x11x2, ... ,xp,1), f(x1,x2, ... ,xp,2), jusqu' f(x11x2, ... ,xp,xp+1). Lorsqu'elle est en train de calculer f(x11x2, ... ,xp,y + 1), le nombre y est cod sur la bande p + 2 et la valeur de f(x11x2, ... ,xp,y) est code sur la bande p + 3: lorsqu'elle se trouve dans l'tat e0, elle transfre le contenu de la bande numro p + 4 sur la bande p + 3 (en effaant la bande numro p + 4) et compare le contenu de la bande p + 2 avec celui de la bande p + 1 (o est inscrit xp+1) : si elle voit que ces nombres sont gaux, elle efface le contenu de la bande p + 2 et s'arrte ; sinon


elle revient en dbut de bande et se met dans l'tat initial de la machine .Jt'; ensuite elle fonctionne comme le ferait cette machine en se servant des bandes numro 1,2, ... ,p,p + 2 et p + 3 comme bandes de donnes et de la bande numro p + 4 pour y crire le rsultat. Lorsque ce dernier calcul est termin, elle ajoute un bton la bande p + 2, replace sa tte en dbut de bande et se remet dans l'tat e0. Le lecteur que cela amuse pourra crire la table N de la machine A" et assigner chacun des nouveaux tats eo e7 un rle prcis.

3.9 Le schma ~: on veut maintenant construire une machine A" qui calcule g(x1,x2, ... ,xp) = J.LY(f(x1,x2, ... ,xp,y) = 0), o fest elle-mme une fonction partielle calcule par une machine .Jt. On va supposer que .Jt a p + 2 + k bandes et que son ensemble d'tats est E. La machine A" a aussi p + 2 + k bandes, son ensemble d'tats est E U { eo,e1,e2,e3,} o eo, e1, e2 et e3 ne sont pas dj dans E ; l'tat initial de A" est le mme que celui de .Jt, et son tat final est e3.

Nous nous contenterons de dcrire le fonctionnement de A" : elle commence travailler exactement comme le ferait .Jt avec les donnes xhx2, ... ,0 ; elle va donc crire le nombre f(xhx2, ... ,xp,O) (si celui-ci est dfini, videmment) sur la bande numro p + 2; elle revient alors en dbut de bande et passe dans l'tat e0. Elle avance sa tte d'une case et examine ce qui est crit sur la deuxime case de la bande p + 2: si c'est un b, le calcul est termin et elle passe dans l'tat e3. Sinon elle passe dans l'tat e1 qui lui fait remplacer le premier blanc qu'elle trouve sur la bande p + 1 par un bton ; elle passe alors dans l'tat e2 qui ramne sa tte en dbut de bande et la remet dans l'tat initial de .Jt. La machine calculera donc successivement f(x1,x2, ... ,xp,O), f(x1,x2, ... ,xp,1) etc. et ne s'arrtera que lorsqu'elle aura trouv O.

3.10 Nous venons donc de terminer la dmonstration du thorme suivant :

THEOREME : Toutes les fonctions partielles rcursives sont T-calculables.

REMARQUE : Il faut bien se persuader que les machines que nous avons dcrites pour calculer les fonctions partielles dfinies par composition, par rcurrence ou par le schma

~ ne se contentent pas de calculer la valeur de ces fonctions lorsqu'elles sont dfinies ; elles ont aussi la proprit de ne pas s'arrter lorsque la fonction en question n'est pas dfinie.


Les fonctions partielles T-calculables sont rcursives

3.11 Pour cette sous-section et les trois suivantes, on fixe une machine de Turing .At et on va supposer que .Jt calcule une fonction partielle f E a-;. Pour montrer que, dans ces conditions, fest rcursive, on va d'abord coder la situation dans laquelle se trouve .At l'instant t par un entier et montrer que ce code est une fonction rcursive primitive de tet des conditions initiales. On aura besoin des fonctions an introduites en 1.11.

Il est bien clair que le nom des tats n'a pas d'importance. Quitte les renommer, on peut supposer que l'ensemble des tats est { 0,1,2, ... ,m }. Pour fixer les ides, disons que l'tat initial est 0 tandis que 1 est l'tat final. En outre, on identifie le symbole blanc avec 0, le symbole de dbut de bande d avec 1 et le bton avec 2.

DEFINITION : Supposons que .Jt possde n bandes. On appelle configuration de .Jt l'instant t la suite infinie C(t) = (s0,s17 ... ,S, ... ) o, pour tous n,u et v (0 :s;; v< n), Snu+v est le symbole crit sur la case numro u + 1 de la bande numro v+ 1 (si est donc un entier compris entre 0 et 2). La sit1111tion de la machine l'instant t est le triplet S(t) = (e,k,C(t)), o e est l'tat o se trouve la machine l'instant t, k Je numro des cases se trouvant devant la tte, et C(t) la configuration de la machine.

Autrement dit, C(t) est la suite obtenue en mettant bout bout les suites ' 1 't ( 1 2 ") j , t 1 b 1 , . 1 , . u1,u2, ... ,Uj ... , ou O'i est a sm e t ,t j, ... ,t i , t 1 etan e sym o e ecnt sur a case numero 1

de la bande numro j. On a dj remarqu que cette suite infinie n'a qu'un nombre fini de termes non blancs (ou non nuls). Les suites infinies de symboles n'ayant qu'un nombre fini de termes non nuls seront codes de la faon suivante: C = (s0,s17 ... ,Sj, ... ), on fera correspondre le code

f(C) = E Sj.3i. i)O

On utilisera ce mme codage pour les suites finies : C = (s0,s 17 . ,sq), on fait correspondre

f(C) = E Sj.3i. O( i (q

Si on connat le code r(C) de la configuration C, on peut facilement retrouver le symbole crit sur une case quelconque des bandes : dsignons respectivement par q(x,y) et r(x,y) le quotient et le reste de la division euclidienne de x par y (si y= 0, on posera arbitrairement q(x,y) = r(x,y) = 0). Le symbole crit sur la case numro u de la bande numro v est

r(q(f(C),3" (u-1) +v-1),3).


On peut tout aussi facilement retrouver la suite u des n symboles crits sur les cases numros u des diffrentes bandes : posons

c(x,y,z) = r(q{x,3z ),3z). Alors, le code r( u) de la suite u est :

r( u) = c(r(C),u,n ). La situationS= (e,k,C) de la machine sera code par l'entier

r(S) = tr:~{e,k,r{C)).

3.12 Le lemme suivant est l'expression du fait que l'on peut dduire la situation de la machine l'instant t + 1 si on connat sa situation l'instant t.

LEMME : Il existe une fonction rcursive primitive gE a-1 telle que, si x est le code de la situation de la machine l'instant t, alors g(x) est le code de la situation de la machine l'instant t + 1.

~ La fonction g est dfinie par cas (exactement 3". (rn + 1) + 1 cas) : pour chaque suite u = (so,s1, .. ,sn-1) d'lments de { 0,1,2} et chaque jE { 0,1, ... ,rn }, on va dcrire ce qui se passe si l'instant t la machine lit la suite u et se trouve dans l'tat j:

L'tat o se trouve la machine, le numro des cases observes et le code de la configuration des bandes sont respectivement {J~(x), {J~(x) et {J~(x). Le code de la suite que la tte est en train de lire est t:{{J~(x),{J~(x),n) = c.

Pour chaque c compris entre 0 et 3" - 1 (ce sont les valeurs que peut prendre r( u) si u est une suite de symboles de longueur n ), et pour chaque j compris entre 0 et rn:

Si {J~(x) = j, si c({J~(x),{J~(x),n) = c, si f{s0,s1, . ,sn-1) = c (autrement dit, pour chaque i compris entre 0 et n - 1, on pose Si= r(q(c,3i),3) = t:{c,i + 1,1)), si M(so,s1 .

Documents

-Logique-mathematique-Tome-II-Rene-Cori.pdf