Advanced topics in theoretical computer science
Slides
30.10.2014: Introduction
[introduction.pdf]
6.11.2014: Turing Machines and Computability (Part 1)
[recap-tm1.pdf]
13.11.2014: Turing Machines and Computability (Part 2)
[recap-tm2.pdf]
(updated after the lecture)
13.11.2013: Register Machines (Part 1)
[register-machines1.pdf]
(updated after the lecture)
20.11.2014: Register Machines (Part 2)
[register-machines2.pdf]
(updated after the lecture)
27.11.2014: Register Machines (Part 3)
[register-machines3.pdf]
(updated after the lecture; last update: December 3: recursive functions in separate file)
27.11.2014: Register Machines: Wrapping up
[register-machines-recap.pdf]
(added on December 3, 2014)
27.11.2014: Recursive functions (Part 1)
[recursive-functions1.pdf]
(after lecture)
4.12.2014: Recursive functions (Part 2)
[recursive-functions2.pdf]
(after the lecture)
11.12.2014: Recursive functions (Part 3)
[recursive-functions3.pdf]
(after the lecture)
18.12.2014: Recursive functions (Part 4)
[recursive-functions4.pdf]
8.01.2015: Computability and (Un-)Decidability, Part I
[computability1.pdf]
15.01.2015: Computability and (Un-)Decidability, Part II
[computability2.pdf]
(we discussed the contents on pages 1-33)
22.01.2015: Computability and (Un-)Decidability, Part III (same slides set as above; we will discuss the contents on pages 33ff)
29.01.2015: Complexity, Part I
[complexity1.pdf]
5.02.2015: Complexity, Part II
[complexity2.pdf]
12.02.2015: Complexity, Part III
[complexity3.pdf]