Skip to Main content Skip to Navigation
Theses

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

Résumé : 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
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

29

Files downloads

41