Skip to Main content Skip to Navigation
New interface
Journal articles

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.
Document type :
Journal articles
Complete list of metadata
Contributor : Walid Gomaa Connect in order to contact the contributor
Submitted on : Wednesday, December 19, 2012 - 4:39:59 PM
Last modification on : Saturday, June 25, 2022 - 7:44:30 PM

Links full text




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



Record views