## Computer Science Research Seminar

** 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.

###

BACK