A survey of recursive analysis and Moore%26apos;s notion of real computation

作者：Gomaa Walid^*

来源：Natural Computing, 2012, 11(1): 37-49.

DOI：10.1007/s11047-011-9278-5

• Recursive analysis
• Turing machine
• GPAC
• Analog computation
• Function algebra

The theory of analog computation aims at modeling computational systems that evolve in a continuous space. 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%26apos;s class of recursive real functions. Recursive analysis was introduced by Turing (Proc Lond Math Soc 2(42):230-265, 1936), Grzegorczyk (Fundam Math 42:168-202, 1955), and Lacombe (Compt Rend l%26apos;Acad Sci Paris 241:151-153, 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 zero-finding. 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%26apos;s class and the relationships between them.

• 出版日期2012-3