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.

Kondensierte Materie

Wenn Atome sich zusammen tun, wird es interessant: Grundlagenforschung an Festkörperelementen, Nanostrukturen und neuen Materialien mit überraschenden Eigenschaften treffen auf innovative Anwendungen.

Kern-, Teilchen-, Astrophysik

Ziel der Forschung ist das Verständnis unserer Welt auf subatomarem Niveau, von den Atomkernen im Zentrum der Atome bis hin zu den elementarsten Bausteinen unserer Welt.

Biophysik

Biologische Systeme, vom Protein bis hin zu lebenden Zellen und deren Verbänden, gehorchen physikalischen Prinzipien. Unser Forschungsbereich Biophysik ist deutschlandweit einer der größten Zusammenschlüsse in diesem Bereich.