Wednesday, March 04, 2009
Prof. Gretchen Ostheimer
Department of Computer Science
Hofstra University
Title:
Decision problems in group theory
Abstract:
In theoretical computer science one of the fundamental questions we study is this one: "For which problems is it possible to write a computer program to solve them, and for which is it not possible to do so?" In the 1930's Alan Turing proved that the so-called Halting Problem is undecidable; loosely speaking, he proved that it is not possible to write a computer program that can test whether a given computer program has an infinite loop in it. This work shook the intellectual world, as it revealed the inherent limitations of computation. Since then decidability has fascinated computer scientists and mathematicians alike. It turns out that group theory, a branch of abstract algebra, is a particularly rich source of examples of both decidable and undecidable problems, and -- even more interesting perhaps -- it is a rich source of examples of problems for which we have been unable (so far) to determine decidability.
In this talk I will describe some of these problems from group theory and the recent progress that we have made in understanding them. No prior knowledge of group theory is assumed, and all students (and faculty) are warmly invited to attend.
This work is joint with Gilbert Baumslag, at the City University of New York, and Chuck Miller, at the University of Melbourne, Australia.
Biography:
Prof. Gretchen Ostheimer has been a member of the computer science faculty at Hofstra since 1999. Her research interests lie on the boundary between theoretical computer science and abstract algebra. More specifically, she is interested in the ways in which theoretical computer science (decidability theory, complexity theory and formal language theory) can help us to better understand infinite groups.