Turing Meets Newton in Chambers Gallery
Following dinner and induction of new members into the Bernard Society, Blum began her talk with introductory computer science concepts, then continued with detailed descriptions of the potential of computability.
Blum is a former vice-president of the American Mathematical Society and a former president and co-founder of the Association for Women in Mathematics. She studied at Carnegie Institute of Technology and later received her Ph.D. from M.I.T. Her career's work has linked seemingly unrelated areas of mathematics and computer science. She has also worked to bridge mathematical communities in Africa, Latin America, and Asia to the United States.
Blum began by describing for her audience the Turing Machine, a prototypical computational device developed by Alan Turing in 1936 which manipulates symbols to solve problems of counting and ordering.
Blum showed examples of the machine's potential.She said that the Turing Machine is the foundation for the theory of computability developed in the '30s, which is itself the foundation for the theory of complexity in computer science developed in the '60s. The Turing Machine, Blum said, created new hope for an understanding of the relative levels of difficulty of some classical problems.
Blum then discussed Newton's Method, an interactive calculus-based algorithm for finding a root of a polynomial, and contrasted it to the type of problems addressed by Turing Machine.
She explained that a Turing Machine deals with problems in a discrete world which can be described to arbitrary precision. But she and her colleagues wanted a model of computation that was more natural for algorithms of numerical analysis, such as Newton's Method. At the same time, however, they searched for a model of computation like the Turing Machine that more naturally conveyed decidability and complexity about sets of real and complex numbers.
Her talk ultimately showed how the theory of computing can be extended to true real number algorithms, instead of exclusively with binary numbers and approximate reals. She cited the Mandelbrot Set as a spectacular graphic image of a question where the theory of computational difficulty should apply, but Turning's theory does not.
She said that her recent book, Complexity and Real Computation, co-authored with Felipe Cucker, Michael Shub, and Steve Smale, focuses on some of these concepts and promises.
The Bernard Society, led this year by president Randy Skattum '01, encourages mathematical discussion on campus through sponsorship of the annual Bernard Lecture, as well as weekly math coffees.