Advanced topics in theoretical computer science
Slides
16.10.2012: Introduction
[introduction.pdf]
25.10.2012: Turing Machines and Computability
[recap-tm.pdf]
; (with white background:
[recap-tm-white.pdf]
)
8.11.2012: Register Machines, Part I
[register-machines1.pdf]
; (with white background:
[register-machines1-white.pdf]
) (28.11.2012: small corrections)
15.11.2012: Register Machines, Part II
[register-machines2.pdf]
; (with white background:
[register-machines2-white.pdf]
) (28.11.2012: small corrections)
22.11.2012: Register Machines: Wrapping up
[register-machines-recap.pdf]
; (with white background:
[register-machines-recap-white.pdf]
)
22.11.2012: Recursive functions, Part I
[recursive-functions1.pdf]
; (with white background:
[recursive-functions1-white.pdf]
)
29.11.2012: Recursive functions, Part II
[recursive-functions2.pdf]
; (with white background:
[recursive-functions2-white.pdf]
)
6.12.2012: Recursive functions, Part III
[recursive-functions3.pdf]
; (with white background:
[recursive-functions3-white.pdf]
)
18.02.2013: Update on page 34
13.12.2012: Recursive functions, Part IV
[recursive-functions4.pdf]
; (with white background:
[recursive-functions4-white.pdf]
)
(14.12.12: Typo in the definition of the Ackermann functions corrected)
(18.12.12: Typo in the definition of the mu operator corrected: like the bounded mu operator it should start from 0, not from 1)
10.01.2013: Computability and (Un-)Decidability, Part I
[computability1.pdf]
; (with white background:
[computability1-white.pdf]
)
17.01.2013: Computability and (Un-)Decidability, Part II
[computability2.pdf]
; (with white background:
[computability2-white.pdf]
) (18.01.2013: corrected typo on page 19 and 27)
(24.01.2013: corrected error in the definition of a Post Normal system and in the example (pages 13,14))
24.01.2013: Complexity, Part I
[complexity1.pdf]
; (with white background:
[complexity1-white.pdf]
)
(18.02.2013: replaced "i >= i" with "i >= 1" in definition of PSPACE on pages 30,31,32)
31.01.2013: Complexity, Part II
[complexity2.pdf]
; (with white background:
[complexity2-white.pdf]
)
(18.02.2013: replaced "i >= i" with "i >= 1" in definition of PSPACE on page 7)
7.02.2013: Complexity, Part III
[complexity3.pdf]
; (with white background:
[complexity3-white.pdf]
)