The elementary computable functions over the real numbers: applying two new techniques |
| |
Authors: | Manuel L Campagnolo Kerry Ojakian |
| |
Institution: | 1. Departamento de Matemática, Instituto Superior de Agronomia, Lisbon University of Technology, Tapada da Ajuda, 1349-017, Lisbon, Portugal 2. SQIG/Instituto de Telecomunica??es, Lisbon, Portugal 3. Departamento de Matemática, Instituto Superior Técnico, Av. Rovisco Pais, 1049-001, Lisbon, Portugal
|
| |
Abstract: | 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 two
techniques we call approximation and lifting. We use these methods to obtain two main theorems. First, we provide an alternative proof of the result from Campagnolo et al.
(J Complex 18:977–1000, 2002), which precisely relates the Kalmar elementary computable functions to a function algebra over
the reals. Second, we build on that result to extend a result of Bournez and Hainry (Theor Comput Sci 348(2–3):130–147, 2005),
which provided a function algebra for the
real elementary computable functions; our result does not require the restriction to functions. In addition to the extension, we provide an alternative approach to the proof. 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 elementary computable functions to a result on the reals. The two
new techniques bring a different perspective to these problems, and furthermore appear more easily applicable to other problems
of this sort.
|
| |
Keywords: | Computable analysis Real recursive functions Elementary computable |
本文献已被 SpringerLink 等数据库收录! |
|