145
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
145
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
AVERTISSEMENT
Ce document est le fruit d’un long travail approuvé par le jury de
soutenance et mis à disposition de l’ensemble de la communauté
universitaire élargie.
Il est soumis à la propriété intellectuelle de l’auteur au même titre que sa
version papier. Ceci implique une obligation de citation et de
référencement lors de l’utilisation de ce document.
D’autre part, toute contrefaçon, plagiat, reproduction illicite entraîne une
poursuite pénale.
Contact SCD INPL: mailto:scdinpl@inpl-nancy.fr
LIENS
Code de la propriété intellectuelle. Articles L 122.4 e la propriété intellectuelle. Articles L 335.2 – L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm
D´epartement de formation doctorale en informatique
Institut National ´Ecole doctorale IAEM Lorraine
Polytechnique de Lorraine
Mod`eles de calcul sur les r´eels
r´esultats de comparaisons
`THESE
pr´esent´ee et soutenue publiquement le 7 d´ecembre 2006
pour l’obtention du
Doctorat de l’Institut National Polytechnique de Lorraine
(sp´ecialit´e informatique)
par
Emmanuel Hainry
Composition du jury
Rapporteurs : Serge Grigorieff Professeur, Universit´e Paris 7
´Giuseppe Longo Directeur de recherche, CNRS & Ecole Normale Sup´erieure, Paris
Examinateurs : Vincent Blondel Professeur, Universit´e catholique de Louvain, Belgique
Olivier Bournez Charg´e de recherche Inria, Nancy
Jos´e F´elix Costa Professeur, Instituto Superior T´ecnico, Lisbonne, Portugal
Jean-Paul Haton Professeur, Universit´e Henri Poincar´e, Nancy
´Jean-Yves Marion Professeur, Ecole des Mines de Nancy
Laboratoire Lorrain de Recherche en Informatique et ses Applications — UMR 7503Remerciements
Denombreusespersonnesm´eritentdesremerciements`adiverstitresparcequ’ellesont
contribu´e `a ce que je puisse r´ealiser ce travail. J’adresse donc des remerciements aux
personnes suivantes.
Jevoudraistoutd’abordremerciermonencadrant,OlivierBournez.Sesconseils´eclai-
´r´es et ´eclairants m’ont guid´e depuis mon stage de dea et tout au long de ma th`ese. Son
optimisme a aussi contribu´e a` faire avancer le travail dans le bon sens.
Je remercie aussi Jean-Yves Marion, mon directeur de th`ese qui a su ˆetre pr´esent aux
bons moments.
Je remercie Serge Grigorieff et Giuseppe Longo qui ont accept´e d’ˆetre les rapporteurs
de cette th`ese.
J’adresse ´egalement mes remerciements a` Vincent Blondel qui m’a fait l’honneur de
pr´esider mon jury de th`ese.
Mes profonds remerciements vont aussi a` Jos´e F´elix Costa qui a accept´e de faire
partie du jury, et qui m’a fait d´ecouvrir de beaux paysages portugais et des points de
vue int´eressants sur le sujet. Mes remerciements vont aussi `a Jean-Paul Haton, r´ef´erent
interne au Loria de mon travail de th`ese.
Je dois aussi remercier Daniel Gra¸ca dont le s´ejour a` Nancy m’a permis de d´ecouvrir
des expressions fran¸caises ´etranges. Le travail avec lui a ´et´e agr´eable et fructueux. Je
remercie ´egalement Manuel Campagnolo qui a aussi particip´e `a ce travail.
Mercia`Antoine,Florent,Germain,Loubna,Romainavecquij’aipartag´emonbureau
mais aussi des id´ees et des doutes.
Plus g´en´eralement, merci `a tous les membres des ´equipes Protheo et Carte pour
m’avoir accueilli au sein de ces ´equipes. Je suis ´egalement reconnaissant au Loria dans
le cadre duquel j’ai pu effectuer ma th`ese confortablement et sans soucis.
Merci aussi `a l’´equipe enseignante du d´epartement d’informatique de l’´ecole des mines
de Nancy.
Je voudrais enfin remercier ma famille et en particulier mes parents.
iRemerciements
iiTable des mati`eres
Remerciements i
Introduction vii
I Prol´egom`enes 1
1 Des mod`eles de calcul discrets aux mod`eles continus 3
1.1 Mod`eles discrets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Machine de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Automates `a deux compteurs . . . . . . . . . . . . . . . . . . . . . 5
1.1.3 Automates cellulaires . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.4 Fonctions r´ecursives . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.5 Th`ese de Church-Turing . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Mod`eles hybrides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.1 Syst`eme dynamique a` temps discret . . . . . . . . . . . . . . . . . 12
1.2.2 Analyse r´ecursive . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.3 Mod`ele bss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Mod`eles continus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.1 General Purpose Analog Computer . . . . . . . . . . . . . . . . . . 15
1.3.2 Machines `a signaux. . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.3 Syst`emes dynamiques `a temps continu . . . . . . . . . . . . . . . . 17
1.3.3.a Syst`emes a` d´eriv´ee constante par morceaux . . . . . . . . 17
1.3.3.b Probl`eme des n corps . . . . . . . . . . . . . . . . . . . . 18
1.3.4 FonctionsR-r´ecursives . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.5 Remarque physique . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.5.a Paradoxe de Z´enon . . . . . . . . . . . . . . . . . . . . . 19
1.3.5.b Int´egration physique . . . . . . . . . . . . . . . . . . . . . 20
2 Compl´ements sur trois mod`eles de calcul sur les r´eels 23
2.1 Analyse r´ecursive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.1 D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.2 D´efinitions adapt´ees . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.3 Propri´et´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2 FonctionsR-r´ecursives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.1 La classeG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.1.a D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . 30
iiiTable des mati`eres
2.2.1.b Propri´et´es . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2.1.c La μ -hi´erarchie . . . . . . . . . . . . . . . . . . . . . . . 35
R
2.2.1.d D´efinitions alternatives . . . . . . . . . . . . . . . . . . . 36
2.2.2 La classeL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.2.2.a D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.2.2.b Propri´et´es . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.2.3 Les classesL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39n
2.2.3.a D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.3.b Propri´et´es . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.3 General Purpose Analog Computer . . . . . . . . . . . . . . . . . . . . . . 40
2.3.1 D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.3.2 Propri´et´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3.3 D´efinitions adapt´ees . . . . . . . . . . . . . . . . . . . . . . . . . . 43
II Comparaison entre fonctions R-r´ecursives et analyse r´ecursive 45
3 Caract´erisation des fonctions r´ecursives par des fonctions R-r´ecursives 47
3.1 Un op´erateur de minimisation r´eel . . . . . . . . . . . . . . . . . . . . . . 47
3.1.1 D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.1.2 Utilisations de ces op´erateurs . . . . . . . . . . . . . . . . . . . . . 49
3.2 Classe capturant les fonctionsR-r´ecursives . . . . . . . . . . . . . . . . . . 50
3.2.1 D´efinitions et propri´et´es basiques . . . . . . . . . . . . . . . . . . . 51
3.2.2 La classeL+!μ capture les fonctions r´ecursives . . . . . . . . . . . 52
3.2.2.a Sens direct de la preuve . . . . . . . . . . . . . . . . . . . 52
3.2.2.b Sens indirect de la preuve . . . . . . . . . . . . . . . . . . 55
3.3 R´esultats concomitants. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.3.1 Inclusion stricte et forme normale . . . . . . . . . . . . . . . . . . 59
3.3.2 Pourquoi la d´efinition de UMU impose la croissance de la fonction 60
3.3.3 Op´erateur de minimum de fonction convexe . . . . . . . . . . . . . 61
3.3.4 Op´erateur de recherche de z´ero sur un compact . . . . . . . . . . . 62
4 Lien entre analyse r´ecursive et fonctions R-r´ecursives 65
4.1 D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 Propri´et´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3 R´esultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3.1 Caract´erisation