About and Around Computing Over the Reals

1. One theory or many? In 2004 a very interesting and readable article by Lenore Blum, entitled “Computing over the reals: Where Turing meets Newton,” appeared in the Notices of the American Mathematical Society. It explained a basic model of computation over the reals due to Blum, Michael Shub and Steve Smale (1989), subsequently exposited at length in their influential book, Complexity and Real Computation (1997), coauthored with Felipe Cucker. The ‘Turing’ in the title of Blum’s article refers of course to Alan Turing, famous for his explication of the notion of mechanical computation on discrete data such as the integers. The ‘Newton’ there has to do to with the well known numerical method due to Isaac Newton for approximating the zeros of continuous functions under suitable conditions that is taken to be a paradigm of scientific computing. Finally, the meaning of “Turing meets Newton” in the title of Blum’s article has another, more particular aspect: in connection with the problem of controlling errors in the numerical solution of linear equations and inversion of matrices,Turing (1948) defined a notion of condition for the relation of changes in the output of a computation due to small changes in the input that is analogous to Newton’s definition of the derivative. The thrust of Blum’s 2004 article was that the BSS model of computation on the reals is the appropriate foundation for scientific computing in general. By way of response, two years later another very interesting and equally readable article appeared in the Notices, this time by Mark Braverman and Stephen Cook (2006) entitled “Computing over the reals: Foundations for scientific computing,” in which the authors argued that the requisite foundation is provided by a quite different “bit computation” model, that is in fact prima facie incompatible with the BSS model. The bit computation model goes back to ideas due to Stefan Banach and Stanislaw Mazur in the latter part of the 1930s, but the first publication was not made until Mazur (1963)..
Keywords No keywords specified (fix it)
Categories No categories specified
(categorize this paper)
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index Translate to english
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 11,371
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA

No references found.

Citations of this work BETA

No citations found.

Similar books and articles
John B. Goode (1994). Accessible Telephone Directories. Journal of Symbolic Logic 59 (1):92-105.
Gordana Dodig-Crnkovic, Semantics of Information as Interactive Computation. Proceedings of the Fifth International Workshop on Philosophy and Informatics 2008.
Gabriele Gramelsberger (2011). What Do Numerical (Climate) Models Really Represent? Studies in History and Philosophy of Science 42 (2):296-302.
Rodney G. Downey & Evan J. Griffiths (2004). Schnorr Randomness. Journal of Symbolic Logic 69 (2):533 - 554.
Paolo Cotogno (2003). Hypercomputation and the Physical Church-Turing Thesis. British Journal for the Philosophy of Science 54 (2):181-223.

Monthly downloads

Added to index


Total downloads

16 ( #104,157 of 1,102,882 )

Recent downloads (6 months)

1 ( #297,281 of 1,102,882 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.