Undecidability [MA5116]
Sommersemester 2012
Information
- Lecture notes updated on June 27.
- No Exercise on July 4.
Exercises
will be discussed on May 2nd, May 9th and then every second week.
Problem set
Content
The course is an introductory course on the limitations to what is computable, decidable or provable. Topics addressed include: recursion theory, basic results by Church, Turing and Gödel, basics of mathematical logic, undecidable problems like the Halting problem, Hilbert’s 10th problem, Post’s correspondence problem, problems related to semigroups, etc. Consequences in computer science, physics and engineering will be outlined.
Literature
The
lecture notes will be continuously updated. The current version is from June 27. The last updated chapter is the one on group presentations.
Additional literature can be found
here