Analog Computation and Function Algebras

Walid Gomaa 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : The first theoretical study of analog computation was published by Shannon in 1941. In this article he proposed the GPAC (General Purpose Analog Computer) as a model for the differential analyzer. Since then there has been a continuous line of research and refinements to that model; see for example Pour-El 1974, Lipshitz and Rubel 1987, and Gra¸ca and Costa 2003. On the other hand classical recursion theory provided another perspective for investigating computation over the real numbers. Recursive analysis was introduced by A. Turing in 1936, and by A. Grzegorczyk and D. Lacombe in 1955. The machine model used is Type 2 Turing machine which is a classical Turing machine equipped with oracles that provide finite approximations of the real arguments. In the context of recursive analysis computability implies continuity. Another development inspired by classical recursion theory is the class of R-recursive functions proposed by C. Moore in 1996. The operations Moore allows in his construction are more or less exact analog correspondences of those generating discrete partial recursive functions, hence the class of R-recursive functions is larger than the class of computable functions given by recursive analysis. For example some discontinuous functions are computable in the former framework. An extensive survey of continuous time models is given by P. Orponen in 1987 and an up-to-date version is given by O. Bournez and M. Campagnolo in 2008. Function algebras provide machine-independent resource-free algebraic characterization of computability and complexity theoretic classes. Many discrete classes have already been characterized by function algebras, most notably the characterization of polynomial time computability in the work of Bellantoni and Cook. There have also been ongoing work for algebraically characterizing real computation within different continuous models and the use of such characterizations to discover relationships among these different models, hence contributing to the effort towards finding a unified theory of real computation. In this presentation we will give a survey of algebraic characterization of real computation within the continuous frameworks mentioned in the previous paragraph.
Type de document :
Communication dans un congrès
The Science and Philosophy of Unconventional Computing, Mar 2009, Cambridge, United Kingdom. 2009
Liste complète des métadonnées
Contributeur : Walid Gomaa <>
Soumis le : vendredi 8 juillet 2011 - 15:42:02
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25


  • HAL Id : inria-00607338, version 1



Walid Gomaa. Analog Computation and Function Algebras. The Science and Philosophy of Unconventional Computing, Mar 2009, Cambridge, United Kingdom. 2009. 〈inria-00607338〉



Consultations de la notice