The Methods of Approximation and Lifting in Real Computation

The basic motivation behind this work is to tie together various computational complexity classes, whether over different domains such as the naturals or the reals, or whether defined in different manners, via function algebras (Real Recursive Functions) or via Turing Machines (Computable Analysis). We provide general tools for investigating these issues, using a technique we call the method of approximation. We give the general development of this method, and apply it to obtain 2 theorems. First we connect the discrete operation of linear recursion (basically equivalent to the combination of bounded sums and bounded products) to linear differential equations, thus providing an alternative proof of the result from Campagnolo, Moore and Costa [M.L. Campagnolo, C. Moore and J. F. Costa, An analog characterization of the Grzegorczyk hierarchy, Journal of Complexity 18 (2002) 977–100]. Secondly, we extend this to prove a result similar to that of Bournez and Hainry [O. Bournez and E. Hainry, Elementarily computable functions over the real numbers and R-sub-recursive functions, Theoretical Computer Science 348 (2005) 130–147], providing a function algebra for the real functions computable in elementary time. Their proof involves simulating the operation of a Turing Machine using a function algebra. We avoid this simulation, using a technique we call “lifting,” which allows us to lift the classic result regarding the Kalmar elementary computable functions to a result on the reals. While we do not claim that our result is necessarily an improvement (perhaps just different), we do want to make the point that our two techniques appear readily applicable to other problems of this sort.