Return to Colloquia & Seminar listing
Undecidability
Student-Run Discrete Math Seminar| Speaker: | Rob Gysel, UC Davis |
| Location: | 2112 MSB |
| Start time: | Thu, Apr 24 2008, 3:10PM |
A core topic in elementary computation theory, undecidability loosely states when it's impossible to construct an algorithm to solve a specified problem. I'll assume no background and will discuss the halting problem, a tiling problem, and Post's correspondence problem if time permits.