Upper and Lower Bounds on Continuous-Time Computation
We consider various extensions and modifications of Shannon's General Purpose Analog Computer, which is a model of computation by differential equations in continuous time. We show that several classical computation classes have natural analog counterparts, including the primitive recursive functions, the elementary functions, the levels of the Grzegorczyk hierarchy, and the arithmetical and analytical hierarchies.
Year of publication: |
2000-06
|
---|---|
Authors: | Campagnolo, Manuel ; Moore, Cristopher |
Institutions: | Santa Fe Institute |
Saved in:
Saved in favorites
Similar items by person
-
Moore, Cristopher, (1995)
-
Quantum Circuits: Fanout, Parity, and Counting
Moore, Cristopher, (1999)
-
Closed-form Analytic Maps in One and Two Dimensions Can Simulate Turing Machines
Koiran, Pascal, (1996)
- More ...