de | en

Unentscheidbarkeit
Undecidability

Modul MA5116

Dieses Modul wird durch Fakultät für Mathematik bereitgestellt.

Diese Modulbeschreibung enthält neben den eigentlichen Beschreibungen der Inhalte, Lernergebnisse, Lehr- und Lernmethoden und Prüfungsformen auch Verweise auf die aktuellen Lehrveranstaltungen und Termine für die Modulprüfung in den jeweiligen Abschnitten.

Basisdaten

MA5116 ist ein Semestermodul in Englisch auf Master-Niveau das unregelmäßig angeboten wird.

Die Gültigkeit des Moduls ist von SS 2011 bis SS 2012.

GesamtaufwandPräsenzveranstaltungenUmfang (ECTS)
150 h 45 h 5 CP

Inhalte, Lernergebnisse und Voraussetzungen

Inhalt

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.

Lernergebnisse

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.

Voraussetzungen

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

Lehrveranstaltungen, Lern- und Lehrmethoden und Literaturhinweise

Lehrveranstaltungen und Termine

Lern- und Lehrmethoden

Vorlesung, Übung

Medienformen

Tafelarbeit

Literatur

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.

Modulprüfung

Beschreibung der Prüfungs- und Studienleistungen

Klausur oder mündliche Prüfung

Wiederholbarkeit

Eine Wiederholungsmöglichkeit wird am Semesterende angeboten.

Nach oben