[FOM] computing over the reals

Stephen Cook sacook at cs.toronto.edu
Tue Sep 20 16:24:52 EDT 2005

Mark Braverman and I have written a survey paper "Computing over the
Reals: Foundations for Scientific Computing" which should be of
interest to some FOM subscribers.  It is available on the arXiv web
site with URL


The abstract appears below.

Stephen Cook

We give a detailed treatment of the ``bit-model'' of computability and
complexity of real functions and subsets of R^n, and argue that this is
a good way to formalize many problems of scientific computation. In the
introduction we also discuss the alternative Blum-Shub-Smale model. In
the final section we discuss the issue of whether physical systems
could defeat the Church-Turing Thesis.

More information about the FOM mailing list