de | en

Undecidability

Module MA5116

This Module is offered by TUM Department of Mathematics.

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 workloadContact hoursCredits (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.

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

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.

Module Exam

Description of exams and course work

Klausur oder mündliche Prüfung

Exam Repetition

The exam may be repeated at the end of the semester.

Top of page