Undecidability [MA5116]

Sommersemester 2012

Prof. Dr. Michael M. Wolf

Dozent:	Prof. Dr. Michael M. Wolf
Übungsleitung:	Dr. Peter Vrana
Mitwirkende:
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

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