https://hal.inria.fr/inria-00607338Gomaa, WalidWalidGomaaCARTE - Theoretical adverse computations, and safety - Inria Nancy - Grand Est - Inria - Institut National de Recherche en Informatique et en Automatique - LORIA - FM - Department of Formal Methods - LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications - Inria - Institut National de Recherche en Informatique et en Automatique - UL - Université de Lorraine - CNRS - Centre National de la Recherche ScientifiqueAnalog Computation and Function AlgebrasHAL CCSD2009[INFO.INFO-OH] Computer Science [cs]/Other [cs.OH]Gomaa, Walid2011-07-08 15:42:022022-06-25 19:41:352011-07-08 15:42:02enConference papers1The 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.