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

There is a possibility to take the exam at the end of the semester.

Condensed Matter

When atoms interact things can get interesting. Fundamental research on the underlying properties of materials and nanostructures and exploration of the potential they provide for applications.

Nuclei, Particles, Astrophysics

A journey of discovery to understanding our world at the subatomic scale, from the nuclei inside atoms down to the most elementary building blocks of matter. Are you ready for the adventure?

Biophysics

Biological systems, from proteins to living cells and organisms, obey physical principles. Our research groups in biophysics shape one of Germany's largest scientific clusters in this area.