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




en fr Computation on the reals.Comparison of some models Modèles de calcul sur les réels, résultats de comparaison - Download this document for free, or read online. Document in PDF available to download.

1 CARTE - Theoretical adverse computations, and safety Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods

Abstract : 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 exist few results for comparing those models, and most of theseresults are incomparability results. The case of computation over the realnumbers hence is quite different from that of computation over integer numberswhere Church-Turing-s thesis claims that all reasonable models compute exactlythe same functions.The results presented in this document are twofold.One, we show that recursively computable functions in the sense ofcomputable analysis can be shown equivalent to some adequately definedsubclass of R-recursive functions, and also to GPAC-computable functionswith GPAC-computable roughly meaning computable through a convergingGPAC. Hence we get a machine independent characterization of recursivelycomputable functions, and a bridge between type 2-machines and GPAC.Two, more than an analog characterization of recursively enumerablefunctions, we show that the limit operator we defined can be used to providean analog characterization of elementarily computable functions andEn-computable functions for n?3, where Enrepresents the levels of Grzegorczyk-s hierarchy.Those results can be seen as a first step toward a unification of computablefunctions over the reals.

Résumé : Il existe de nombreux modèles de calcul sur les réels. Ces différents modèlescalculent diverses fonctions, certains sont plus puissants que d-autres,certains sont deux à deux incomparables. Le calcul sur les réels est donc dece point de vue bien différent du calcul sur les entiers qui est unifié par lathèse de Church-Turing qui affirme que tous les modèles raisonnables calculentles mêmes fonctions.Les résultats de cette thèse sont de deux sortes. Premièrement, nousmontrons des équivalences entre les fonctions récursivement calculables et unecertaine classe de fonctions R-récursives et entre les fonctionsGPAC-calculables et les fonctions récursivement calculables. Ces deuxrésultats ne sont cependant valables que si les fonctions présentent quelquescaractéristiques : elles doivent être définies sur un compact et dans lepremier cas être de classe C^2. Deuxièmement, nous montrons également unehiérarchie de classes de fonctions R-récursives qui caractérisent lesfonctions élémentairement calculables, les fonctionsEn-calculables pour n?3 où les En sont lesfonctions de la hiérarchie de Grzegorczyk, et des fonctions récursivementcalculables. Ce résultat utilise un opérateur de limite dont nous avons prouvéla généralité en montrant qu-il transfère une inclusion sur la partie discrètedes fonctions en une inclusion sur les fonctions sur les réels elles-mêmes.Ces résultats constituent donc une avancée vers une éventuelleunification des modèles de calcul sur les réels.

en fr

Keywords : Recursive analysis analog computation elementary functions Grzegorczyk hierarchy

Mots-clés : Analyse récursive calculabilité réelle fonctions élémentaires hiérarchie de Grzegorczyk General Purpose Analog Computer





Author: Emmanuel Hainry -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents