Decidability, Computability, and Complexity (EBK)

Understand the Limits of Computation: Explore computability, decidability, and computational complexity theory while analyzing fundamental questions in computer science—from Turing machines and the Halting Problem to NP-completeness and the P vs. NP problem. Learn to recognize and classify the fundamental limits of algorithmic problem solving.

Contents

• Computability and complexity theory are among the central foundations of theoretical computer science. At their core lie questions such as: What can be computed algorithmically at all? How costly is a given computation? And are there problems that cannot be solved in principle? The most famous—and by far the most significant—unsolved problem in theoretical computer science is the P versus NP problem, which asks whether every problem whose solution can be efficiently verified can also be solved efficiently. This problem will also be part of the lecture.The course conveys fundamental knowledge of computability, decidability, and complexity. Among other things, we will cover:
• the abstract model of a computer—the Turing machine
• the intuitive notion of computability and the Church–Turing thesis
• primitive recursive and $\mu$-recursive functions
• recursive and recursively enumerable languages
• the halting problem
• the most important complexity classes (including P and NP)A particular connection exists to artificial intelligence: the historical roots of computability theory—especially the work of Alan Turing—are closely tied to the idea of machine intelligence. The two fields also intersect in substance: the security of modern AI systems, for instance, often relies on the assumption that certain problems cannot be solved efficiently in practice (P $\neq$ NP). Moreover, the question of whether the behavior of complex AI systems can be reliably predicted bears structural parallels to the halting problem.

Competencies

Students are able to

• explain the concept of turing machines and to apply it to current problems
• explain the conepts of undecidability to non-experts using examples
• know and to apply central concepts and methods of complexity theory
• explain the concept of computability
• be able to understand current research literature and topics

Literature

• M. Aigner, "Diskrete Mathematik", 6th corrected ed. Wiesbaden, Germany: Springer Vieweg, 2006.
• J. Hromkovič, "Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography" (Texts in Theoretical Computer Science. An EATCS Series). Berlin, Germany: Springer, 2004.
• O. Goldreich, "Computational Complexity: A Conceptual Perspective". Cambridge, U.K.: Cambridge Univ. Press, 2008.
• J. E. Hopcroft, R. Motwani, and J. D. Ullman, "Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit", 3rd ed. Munich, Germany: Pearson Studium, 2011.
• K. R. Reischuk, "Komplexitätstheorie – Band I: Grundlagen: Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus", 2nd rev. and enlarged ed. Wiesbaden, Germany: Vieweg+Teubner, 1999.
• I. Wegener, "Complexity Theory: Exploring the Limits of Efficient Algorithms", R. Pruim, Transl. Berlin, Germany: Springer, 2005.
• S. Arora and B. Barak, "Computational Complexity: A Modern Approach". Cambridge, U.K.: Cambridge Univ. Press, 2009.
• D. C. Kozen, "Theory of Computation" (Texts in Computer Science). London, U.K.: Springer, 2006.
• N. Cutland, "Computability: An Introduction to Recursive Function Theory". Cambridge, U.K.: Cambridge Univ. Press, 1980.
• R. G. Downey and M. R. Fellows, "Fundamentals of Parameterized Complexity" (Texts in Computer Science). London, U.K.: Springer, 2013.
• Z. Hou, "Fundamentals of Logic and Computation: With Practical Automated Reasoning and Verification" (Texts in Computer Science). Cham, Switzerland: Springer, 2021.
• A. Pettorossi, "Automata Theory and Formal Languages: Fundamental Notions, Theorems, and Techniques". Cham, Switzerland: Springer, 2022.
• H. Chen, "Computability and Complexity". Cambridge, MA, USA: MIT Press, 2023.
• K. R. Chowdhary, "Theory of Computation: Automata, Formal Languages, Computation and Complexity". Singapore: Springer, 2025.

Lecturer

• Prof. Dr. Lutz Strüngmann

Recommended Previous Knowledge 

• Math for Computer Scientists 1 (MA1)
• Math for Computer Scientists 2 (MA2)
• Math for Computer Scientists 3 (MA3)

Module Details

Semester	1/2
Lecture Language	German and English
Frequency	Not regularly
Credit Points (ECTS)	5
Course Coordinator	Prof. Dr. Lutz Strüngmann
Duration	1 Semester
Course Achievement	None
Prerequisite for exam	Compulsory Assignment (PU)
Exam	Written Exam 90 Minutes (K90)

Weekly Hours (SWS) 

Lecture	2 SWS
Exercises	2 SWS
Sum	4 SWS

Work Load 

Lecture	45 h
Self Study	70 h
Assignments	15 h
Exam Preparation	20 h
Sum	150 h