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])