About and Around Computing Over the Reals
| Abstract | 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 (fix it) | |||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,882 |
| External links |
  Try with proxy. |
| Through your library | Only published papers are available at libraries |
Similar books and articlesFelipe Cucker & Klaus Meer (1999). Logics Which Capture Complexity Classes Over the Reals. Journal of Symbolic Logic 64 (1):363-390.
John B. Goode (1994). Accessible Telephone Directories. Journal of Symbolic Logic 59 (1):92-105.
Dina Goldin & Peter Wegner (2008). The Interactive Nature of Computing: Refuting the Strong Church–Turing Thesis. Minds and Machines 18 (1).
Peter Kugel (2002). Computing Machines Can't Be Intelligent (...And Turing Said So). Minds and Machines 12 (4):563-579.
Hava T. Siegelmann (2003). Neural and Super-Turing Computing. Minds and Machines 13 (1):103-114.
Gordana Dodig-Crnkovic, Semantics of Information as Interactive Computation. Proceedings of the Fifth International Workshop on Philosophy and Informatics 2008.
Graham White (2013). Notions of Information: Remarks on Fresco's Paper. Philosophy and Technology 26 (1):61-65.
B. Maclennan (2003). Transcending Turing Computability. Minds and Machines 13 (1):3-22.
Matti Tedre (2011). Computing as a Science: A Survey of Competing Viewpoints. Minds and Machines 21 (3):361-387.
Gordana Dodig-Crnkovic (2011). Significance of Models of Computation, From Turing Model to Natural Computation. Minds and Machines 21 (2):301-322.
Gabriele Gramelsberger (2011). What Do Numerical (Climate) Models Really Represent? Studies in History and Philosophy of Science 42 (2):296-302.
B. Jack Copeland & Oron Shagrir (2007). Physical Computation: How General Are Gandy's Principles for Mechanisms? Minds and Machines 17 (2).
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.
Analytics
Monthly downloads |
Added to index2011-05-18Total downloads16 ( #75,695 of 556,916 )Recent downloads (6 months)1 ( #64,931 of 556,916 )How can I increase my downloads? |
My notes
Discussion
