Upper and lower bounds on continuous-time computation

Manuel Lameiras Campagnolo and Cristopher Moore

Proc. 2nd International Conference on Unconventional Models of Computation, 135-153.

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.

Click here to download

Cris Moore <moore@santafe.edu>