## CSC Colloquium: Steven Lindell

## Computation: A Mathematical or Physical Notion?

Time: Monday, November 05, 2007 at 04:30 PMDr. Steven Lindell, Haverford College - Department of Computer Science

#### Abstract:

Models of computation such as the Turing machine are based on the idealized psychological characteristics of a human calculator -- an autonomous machine that changes its "state of mind" in a stepwise fashion based on the recognition of symbolic cellular configurations. This leads to a mathematical model of effective computability, and its complexity is traditionally quantified by measuring the amount of time (steps) and space (cells) required in the computation. However, a concrete model of computation must use matter and energy, operating under natural constraints governed by the laws of physics. This leads to a new notion of feasibility based on physical resources, particularly when the laws of thermodynamics and gravitation are taken into account.

#### Speaker Bio:

Dr. Steven Lindell, Haverford College - Department of Computer Science

Steven Lindell founded the Computer Science Department at Haverford College, and is currently a full professor there. He received his B.A. and M.A. in Mathematics at UCLA, and went on to receive a Ph.D. in theoretical Computer Science at UCLA under the supervision of Sheila Greibach and Yiannis Moschovakis in 1987, on the topic of mathematical logic and computational complexity. His current interests include finding a logical characterization of the fundamental physical limitations of mechanical computing devices. The recipient of four National Science Foundation grants for a period of fifteen years, he has published over a dozen papers in the area of mathematical logic applied to computational complexity, and given over twenty talks. The talk planned for today is based on one he gave at the Isaac Newton Institute for Mathematical Sciences last year.

Refreshments will be served in MSC 159 after the talk.