An Analog Characterization of the Subrecursive Functions

Manuel Lameiras Campagnolo, Cristopher Moore and José Félix Costa

Working Papers from Santa Fe Institute

Abstract: We study a restricted version of Shannon's General Purpose Analog Computer in which we only allow the machine to solve linear differential equations. This corresponds to only allowing local feedback in the machine's variables. We show that if this computer is allowed to sense inequalities in a differentiable way, then it can compute exactly the elementary functions. Furthermore, we show that if the machine has access to an oracle which computes a function f(x) with a suitable growth as x goes to infinity, then it can compute functions on any given level of the Grzegorczyk hierarchy. More precisely, we show that the model contains exactly the nth level of the Grzegorczyk hierarchy if it is allowed to solve n-3 non-linear differential equations of a certain kind. Therefore, we claim that there is a close connection between analog complexity classes, and the dynamical systems that compute them, and classical sets of subrecursive functions.

Keywords: Analog computation; differential equations and recursion theory. (search for similar items in EconPapers)
Date: 2000-01
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:00-01-005

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().