Computability

---

So we have discussed about many different machines and their computational abilities. Now, we want to understand the limits of what can be computed. This leads us to the concept of computability theory, which studies which problems can be solved by algorithms and which cannot. We will explore fundamental questions like: What problems are algorithmically solvable? What makes some problems inherently unsolvable by any computer?

This module has the following key topics:

• The Church-Turing Thesis
• Undecidable problems
• Rice’s Theorem
• Reduction techniques
• The Halting Problem
• Computable vs. non-computable functions
• Universal machines and diagonalization
• …