Vertiefung Theoretische Informatik

Instructor:
  • Viorica Sofronie-Stokkermans <sofronie@uni-koblenz.de>
  • 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]


    Contents

    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