Undecidability
Module MA5116
This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.
Basic Information
MA5116 is a semester module in English language at Master’s level which is offered irregular.
This module description is valid from SS 2011 to SS 2012.
| Total workload | Contact hours | Credits (ECTS) |
|---|---|---|
| 150 h | 45 h | 5 CP |
Content, Learning Outcome and Preconditions
Content
The course deals with the limitations to what is computable or provable.
Topics addressed are: automata and languages, recursion theory, basic results by Church, Turing and Gödel, undecidable problems incl. the Halting problem, Hilbert's 10th problem, Post's correspondence problem and problems related to semigroups.
Consequences in computer science, physics and engineering will be outlined.
Topics addressed are: automata and languages, recursion theory, basic results by Church, Turing and Gödel, undecidable problems incl. the Halting problem, Hilbert's 10th problem, Post's correspondence problem and problems related to semigroups.
Consequences in computer science, physics and engineering will be outlined.
Learning Outcome
At the end of the module, students are able to analyse computational problems regarding their decidability. They are familiar with some of the most prominent undecidable problems as well as with their computable counterparts.
Preconditions
MA1101 Lineare Algebra 1, MA1102 Lineare Algebra 2, MA1001 Analysis 1, MA1002 Analysis 2, familiarity with any computer programming language as well as with basic notions of logic is recommended
Courses, Learning and Teaching Methods and Literature
Courses and Schedule
| Type | SWS | Title | Lecturer(s) | Dates | Links |
|---|---|---|---|---|---|
| VO | 2 | Undecidability | Wolf, M. | ||
| UE | 1 | Exercises for Undecidability | Wolf, M. |
Learning and Teaching Methods
Vorlesung, Übung
Media
Tafelarbeit
Literature
M. Sipser, Introduction to the theory of computation,Thomson Course Technology;
N. Cutland, Computability, Cambridge University Press;
H. Rogers, Theory of Recursive Functions and Effective Computability, MIT press.
N. Cutland, Computability, Cambridge University Press;
H. Rogers, Theory of Recursive Functions and Effective Computability, MIT press.