Vertiefung Theoretische Informatik

  • Viorica Sofronie-Stokkermans <>
  • Exercise
  • Slides
  • Exercise Sheets
  • Newsgroup: infko.theoinf

  • Exam: Written (duration 2 h) or oral, dependig on the number of participants.

    List of topics: [summary.pdf]


    This lecture presents important notions and results related to computability and its limits.
  • Turing Machines and Turing Computability
  • Register machines (LOOP, WHILE, GOTO)
  • Recursive functions
  • The Church-Turing Thesis
  • Computability and (Un-)decidability
  • Complexity