5:15 pm,
Thursday,
April 11, 2013

Science 106

## Science Speakers {Is There Anything Computers Can't Do?!}

Thursday, April 11, 5:15 - 6:15 PM in Science Hall 106

Is There Anything Computers Can't Do?! Abstract: (Hint: Yes). We will explore an 80-year-old field of mathematics and computer science known as "computability." The goal of computability is simple: which problems can be solved in an "effective" manner. Usually, this boils down to determining for which problems does there exist an algorithm to solve them. For example: suppose we have a polynomial with integer coefficients. Is there a sure-fire way to determine whether or not its roots are all rational numbers or not? It turns out that there is no such algorithm, and this is an "undecidable" problem!

We will give the basics of computability through the idea of Turing machines. Focusing on functions on the natural numbers, we will explore some "computable" functions and "non-computable" functions. We will give a bit of historical context for computability, giving examples of how it has affected mathematics and computer science. Finally, we will introduce an exciting area of mathematics with many open problems known as "computable structure theory."

Jesse Johnson, University of Notre Dame

**Contact:** David Housman, phone 7061, email *dhousman@goshen.edu*