Real-Valued, Continuous-Time Computers: A Model of Analog Computations, Part I

Christopher Moore

Working Papers from Santa Fe Institute

Abstract: We develop a system of recursive functions on the reals analogous to classical recursion theory on the natural numbers. This system turns out to include many sets and functions that are uncomputable in the traditional sense.

These functions can be computed by an idealized computer that runs on continuous states in continous time; however, this computer turns out to be highly unphysical. Looking more closely, we find that we can stratify these functions according to how many idealizations or infinite limits they are away from physical computability.

We conclude that, in a certain sense, finite-dimensional analog computation is more powerful than digital computation: however, physically realizable analog computation would seem to be equivalent. Thus the {\it Physical Church-Turing Thesis}, that no physical computer is more powerful than a Turing machine, is false in a perfect, classical world but probably ture in the world we live in.

Date: 1993-04
References: Add references at CitEc
Citations:

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:93-04-018

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 ().