A characterization of computable analysis on unbounded domains using differential equations
The functions of computable analysis are defined by enhancing normal Turing machines to deal with real number inputs. We consider characterizations of these functions using function algebras, known as real recursive functions. Since there are numerous incompatible models of computation over the reals, it is interesting to find that the two very different models we consider can be set up to yield exactly the same functions. Bournez and Hainry used a function algebra to characterize computable analysis, restricted to the twice continuously differentiable functions with compact domains. In our earlier paper, we found a different (and apparently more natural) function algebra that also yields computable analysis, with the same restriction. In this paper we improve earlier work, finding three function algebras characterizing computable analysis, removing the restriction to twice continuously differentiable functions and allowing unbounded domains. One of these function algebras is built upon the widely studied real primitive recursive functions. Furthermore, the proof of this paper uses our previously developed method of approximation, whose applicability is further evidenced by this paper. (C) 2011 Elsevier Inc. All rights reserved.
computable analysis differential equations function algebras real recursive functions analog computation