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.
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
P. Odifreddi, Classical Recursion Theory, Studies in Logic, North Holland 1989