Georgia Institute of Technology Georgia Tech Algorithm and Randomness Center (ARC)

Alan Turing and the Other Theory of Computation

Lenore Blum

Distinguished Career Professor of Computer Science

Carnegie Mellon University

Abstract

Most logicians and theoretical computer scientists are familiar with Alan Turing’s 1936 seminal paper setting the stage for the foundational (discrete) theory of computation. Most however remain unaware of Turing’s 1948 seminal paper which introduces the notion of condition, setting the stage for a natural theory of complexity for the “other theory of computation.”

Computational mathematics, the “other theory of computation,” emanates from the classical tradition of numerical analysis, equation solving and the continuous mathematics of calculus. 

This talk will recognize Alan Turing’s work in the foundations of numerical computation (in particular, his 1948 paper “Rounding-Off Errors in Matrix Processes”), its influence in complexity theory today, and how it provides a unifying concept for the two major traditions of the Theory of Computation.

Bio

Lenore Blum (PhD, MIT) is Distinguished Career Professor of Computer Science at Carnegie Mellon and Founding Director of Project Olympus, an innovation center that works with faculty and students to bridge the gap between cutting-edge university research/innovation and economy-promoting commercialization for the benefit of our communities. Project Olympus is a good example of Blum’s determination to make a real difference in the academic community and the world beyond.

Lenore is internationally recognized for her work in increasing the participation of girls and women in Science, Technology, Engineering, and Math (STEM) fields. She was founding co-Director of the Math/Science Network and its Expanding Your Horizons conferences for middle and high school girls. At CMU she founded the Women@SCS program and CS4HS, now sponsored world-wide by Google.  In 2004 she received the US Presidential Award for Excellence in Science, Mathematics, and Engineering Mentoring.  In 2009 she received the Carnegie Science Catalyst Award recognizing her work targeting high-tech talent to promote economic growth in the Pittsburgh region and for increasing the participation of women in computer science.

Lenore’s research, from her early work in model theory and differential fields (logic and algebra) to her more recent work in developing a theory of computation and complexity over the real numbers (mathematics and computer science), has focused on merging seemingly unrelated areas. The latter work, founding a theory of computation and complexity over continuous domains, forms a theoretical basis for scientific computation.  On the eve of Alan Turing’s 100^th birthday in June 2012, she was plenary speaker at the Turing Centenary Celebration at the University of Cambridge, England, showing how a little known (to logicians!) paper of Turing’s is fundamental to this theory. She will amplify this perspective in her Georgia Tech talk.

Oct. 27 at 5 p.m.

Howey Physics Bldg. L4