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

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 “Physical Church-Turing Thesis,” that no physical computer is more powerful than a Turing machine, is false in a perfect, classical world but probably true in the world we live in.