Vertiefung Theoretische Informatik

Instructor:
  • Viorica Sofronie-Stokkermans <sofronie@uni-koblenz.de>
    • Exercise
  • Slides
  • Exercise Sheets
  • Newsgroup: infko.theoinf
    • Exam: Written exam, duration 2 h.

  • Termin 1: Thursday, 26.02.2015, 13:00-15:00, Room M001
  • Question/Answer Session: 24.02.2015, 13:00 s.t., Room B 016.
  • List of topics: [summary.pdf] (correction concerning the theorem of Rice, 19.02.2015)
  • Termin 2: 13.04.2015, 16:00 s.t., D 239.

    • 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
  • If time remains: other computation models (e.g. automata over infinite words)