A Survey of Recursive Analysis and Moore's Notion of Real Computation

Walid Gomaa 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : The theory of analog computation aims at modeling computational systems that evolve in a continuous manner. Unlike the situation with the discrete setting there is no unified theory of analog computation. There are several proposed theories, some of them seem quite orthogonal. Some theories can be considered as generalizations of the Turing machine theory and classical recursion theory. Among such are recursive analysis and Moore's class of recursive real functions. Recursive analysis was introduced by A. Turing [1936], A. Grzegorczyk [1955], and D. Lacombe [1955]. Real computation in this context is viewed as effective (in the sense of Turing machine theory) convergence of sequences of rational numbers. In 1996 Moore introduced a function algebra that captures his notion of real computation; it consists of some basic functions and their closure under composition, integration and zerofinding. Though this class is inherently unphysical, much work have been directed at stratifying, restricting, and comparing it with other theories of real computation such as recursive analysis and the GPAC. In this article we give a detailed exposition of recursive analysis and Moore's class and the relationships between them.
Type de document :
Article dans une revue
Natural Computing, Springer Verlag, 2012, 11 (1), pp.37-49. 〈10.1007/s11047-011-9278-5〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00767334
Contributeur : Walid Gomaa <>
Soumis le : mercredi 19 décembre 2012 - 16:39:59
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25

Identifiants

Collections

Citation

Walid Gomaa. A Survey of Recursive Analysis and Moore's Notion of Real Computation. Natural Computing, Springer Verlag, 2012, 11 (1), pp.37-49. 〈10.1007/s11047-011-9278-5〉. 〈hal-00767334〉

Partager

Métriques

Consultations de la notice

119