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 (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
Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 29,174
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.

Add more references

Citations of this work BETA
The Representational Foundations of Computation.Michael Rescorla - 2015 - Philosophia Mathematica 23 (3):338-366.

Add more citations

Similar books and articles
Logics Which Capture Complexity Classes Over the Reals.Felipe Cucker & Klaus Meer - 1999 - Journal of Symbolic Logic 64 (1):363-390.
Accessible Telephone Directories.John B. Goode - 1994 - Journal of Symbolic Logic 59 (1):92-105.
Neural and Super-Turing Computing.Hava T. Siegelmann - 2003 - Minds and Machines 13 (1):103-114.
Semantics of Information as Interactive Computation.Gordana Dodig-Crnkovic - 2008 - Proceedings of the Fifth International Workshop on Philosophy and Informatics 2008.
Notions of Information: Remarks on Fresco's Paper.Graham White - 2013 - Philosophy and Technology 26 (1):61-65.
Transcending Turing Computability.B. Maclennan - 2003 - Minds and Machines 13 (1):3-22.
What Do Numerical (Climate) Models Really Represent?Gabriele Gramelsberger - 2011 - Studies in History and Philosophy of Science Part A 42 (2):296-302.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Hypercomputation and the Physical Church-Turing Thesis.Paolo Cotogno - 2003 - British Journal for the Philosophy of Science 54 (2):181-223.
Added to PP index

Total downloads
51 ( #104,281 of 2,180,223 )

Recent downloads (6 months)
1 ( #304,931 of 2,180,223 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature

There  are no threads in this forum
Nothing in this forum yet.

Other forums