Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage fortgeschnittene Beweise aus der Berechenbarkeitstheorie unabhängig durchzuführen und dafür verschiedene vorgetragene Theoreme anzuwenden.

Introduction to computability theory: unsolvable problems, models of computations (Turing machines, register machines, recursive functions, lambda calculus), Church-Turing thesis, numbering of computable functions, numbering programs, the diagonal method, the s-m-n theorem, universal programs, Kleene's theorem, recursive and recursively enumerable sets, Rice's theorem. Die LOOP-Hierarchie und Aufzaehlungen subrecursiver Klassen. Didaktisches Vorgehen: Zu der Vorlesung werden 2 Uebungsblaetter verteilt, welche von den Studenten selbstaendig zu loesen sind. Abschliessende muendliche Pruefung.

Vortrag 

Aufwandsabschaetzung

24 h: 6-8 Vorlesungseinheiten

16 h: Loesen von 2 Uebungsblaettern a 7 Beispielen

4 h: tippen der Loesung in LaTeX

30 h: Vorbereitung auf abschliessende Pruefung

1 h: abschl. Pruefung

---------------------------------------------------

75 Std  = 3 ECTS

2 Übungsblätter und eine mündliche Prüfung

P. Odifreddi, Classical Recursion Theory, Studies in Logic, North Holland 1989

Grundkenntnisse der mathematischen Logik und der Theoretischen Informatik. Im besonderen sind Grundkenntnisse der Praedikatenlogik erforderlich