Modèles de calcul sur les réels, résultats de comparaison

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 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
Document type :
Theses
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download

https://hal.univ-lorraine.fr/tel-01752781
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 1:57:51 PM
Last modification on : Tuesday, April 24, 2018 - 1:30:13 PM

File

2006_HAINRY_E.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01752781, version 1

Collections

Citation

Emmanuel Hainry. Modèles de calcul sur les réels, résultats de comparaison. Autre [cs.OH]. Institut National Polytechnique de Lorraine, 2006. Français. ⟨NNT : 2006INPL090N⟩. ⟨tel-01752781⟩

Share

Metrics

Record views

19

Files downloads

21