Il existe de nombreux modèles de calcul sur les réels. Ces différents modèles<br />calculent diverses fonctions, certains sont plus puissants que d'autres,<br />certains sont deux à deux incomparables. Le calcul sur les réels est donc de<br />ce point de vue bien différent du calcul sur les entiers qui est unifié par la<br />thèse de Church-Turing qui affirme que tous les modèles raisonnables calculent<br />les mêmes fonctions.<br /><br />Les résultats de cette thèse sont de deux sortes. Premièrement, nous<br />montrons des équivalences entre les fonctions récursivement calculables et une<br />certaine classe de fonctions R-récursives et entre les fonctions<br />GPAC-calculables et les fonctions récursivement calculables. Ces deux<br />résultats ne sont cependant valables que si les fonctions présentent quelques<br />caractéristiques : elles doivent être définies sur un compact et dans le<br />premier cas être de classe C^2. Deuxièmement, nous montrons également une<br />hiérarchie de classes de fonctions R-récursives qui caractérisent les<br />fonctions élémentairement calculables, les fonctions<br />En-calculables pour n?3 (où les En sont les<br />fonctions de la hiérarchie de Grzegorczyk), et des fonctions récursivement<br />calculables. Ce résultat utilise un opérateur de limite dont nous avons prouvé<br />la généralité en montrant qu'il transfère une inclusion sur la partie discrète<br />des fonctions en une inclusion sur les fonctions sur les réels elles-mêmes.<br /><br />Ces résultats constituent donc une avancée vers une éventuelle<br />unification des modèles de calcul sur les réels.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00142675 |
| Date | 07 December 2006 |
| Creators | Hainry, Emmanuel |
| Publisher | Institut National Polytechnique de Lorraine - INPL |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0024 seconds