Modèles de calcul sur les réels, résultats de comparaison, Computation on the reals. Comparison of some models

Emmanuel Hainry

Description

Sous la direction de Jean-Yves Marion, Olivier Bournez
Thèse soutenue le 07 décembre 2006: INPL
Il existe de nombreux modèles de calcul sur les réels. Ces différents modèles calculent diverses fonctions, certains sont plus puissants que d'autres, certains sont deux à deux incomparables. Le calcul sur les réels est donc de ce point de vue bien différent du calcul sur les entiers qui est unifié par la thèse de Church-Turing affirmant que tous les modèles raisonnables calculent les mêmes fonctions. Nous montrons des équivalences entre les fonctions récursivement calculables et une certaine classe de fonctions R-récursives et entre les fonctions GPAC-calculables et les fonctions récursivement calculables. Nous montrons également une hiérarchie de classes de fonctions R-récursives qui caractérisent les fonctions élémentairement calculables, les fonctions de la hiérarchie de Grzegorczyk et les fonctions récursivement calculables à l'aide d'un opérateur de limite. Ces résultats constituent donc une avancée vers une éventuelle unification des modèles de calcul sur les réels
-Analyse récursive
-Calculabilité réelle
-Fonctions élémentaires
-Hiérarchie de Grzgorczyk
-General Purpose Computer
Computation on the real numbers can be modelised in several different ways. There indeed exist a lot of different computation models on the reals. However, there are few results for comparing those models, and most of these results are incomparability results. The case of computation over the reals hence is quite different from the classical case where Church thesis claims that all reasonable models compute exactly the same functions. We show that recursively computable functions (in the sense of computable analysis) can be shown equivalent to some adequately defined class of R-recursive functions, and also to GPAC-computable functions. More than an analog characterization of recursively enumerable functions, we show that the limit operator we defined can be used to provide an analog characterization of elementarily computable functions and functions from Grzegorczyk's hierarchy. Those results can be seen as a first step toward a unification of computable functions over the reals
-Recursive analysis
-Analog computation
-Elementary functions
-Grzgorczyk hierarchy
-General Purpose Analog Computer
Source: http://www.theses.fr/2006INPL090N/document

Informations

• Publié par: Thesee
• Nombre de lectures: 31
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

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:[e-mail]




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