BannerHauptseite TUMHauptseite LehrstuhlMathematik SchriftzugHauptseite LehrstuhlHauptseite Fakultät

Undecidability [MA5116]

Sommersemester 2012

Prof. Dr. Michael M. Wolf

Dozent: Prof. Dr. Michael M. Wolf
Übungsleitung: Dr. Peter Vrana
Vorlesung: Mo 14:00 - 16:00 Seminarraum 03.10.011 Anmeldung
Zentralübung: Mi 16:15 - 17:45 Seminarraum 03.10.011 Anmeldung
Tutorübungen:   Anmeldung



will be discussed on May 2nd, May 9th and then every second week.

Problem set


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.


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 Pfeil