Home

Even in a world that AI is ubiquitous, the fundamental principles of computation remain as relevant as ever. This note delves into the core concepts of computational theory, exploring the limits of what machines can and cannot do.

Textbook

Michael Sipser - Introduction to the Theory of Computation - Course Technology (2012)

Grade

  • 50% - Homework
  • 50% - Final Exam

Outline

  • Automata Theory
    • Do these models have the same power, or can one do more than the other?
  • Computability Theory
    • Classify problems as being solvable or not
  • Complexity Theory
    • Classify problems as being easy or hard