Computing over the Reals: Where Turing Meets Newton

The classical (Turing) theory of computation has been extraordinarily successful in providing the foundations and framework for theoretical computer science. But its dependence on 0's and 1's is fundamentally inadequate for providing such a foundation for modern scientific computation where most algorithms are real number algorithms. In this program, Lenore Blum discusses the results of work that indicates how basic notions from numerical analysis are being introduced into complexity theory, bringing together ideas germinating from the real calculus of Newton and the discrete computation of computer science.