[FOM] computing over the reals
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.
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