Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

An Introduction to the Theory of Computation

Student-Run Research Seminar

Speaker: Brad Ballinger, UC Davis
Location: 693 Kerr
Start time: Wed, Nov 7 2001, 12:00PM

Sometimes rather than producing an explicit solution to a problem, it is sufficient to produce an algorithm (or better, a computer program) for solving it. I will talk about a few basics from the theory of computation, including:

* The century-old question that started it all

* The definition of a Turing machine

* What is a decidable question?

* What are P and NP, and why are they important?

I plan to keep it simple, but still prove at least one big result.