Computability Theory: Computable Functions and Decidable Sets

Explore the core principles that define what computers can and cannot solve. This text-based course introduces theoretical computer science and computability theory in an approachable, step-by-step format. By following clear written explanations and rigorous conceptual breakdowns, you will gain a strong grasp of algorithmic decidability, formal computability, and the theoretical boundaries of modern computing. What you'll learn: - Understand core mathematical definitions of computable functions and algorithms - Explore decidable sets and computably enumerable sets - Master Post's theorem and its applications in set theory - Examine the construction and significance of universal computable functions - Analyze classic undecidable problems and unextendable partial computable functions - Connect fundamental computability concepts to modern formal logic and complexity theory The course begins with fundamental terminology and basic set-theoretic principles before progressing to proofs, universal functions, and unsolvability. Designed for beginners in theoretical computer science, logic, or discrete mathematics, no prior advanced knowledge is required. Start reading to develop your theoretical understanding of computation.