Automata, Formal Languages, and Computational Complexity
Over the course of your journey through computation, you may have noticed that many problems can be solved with the same solution, using a skill you have honed called abstraction. Through this process, you may have noticed more nuanced connections between problems. Some problems require some translation before the solution to another problem can be applied. Other problems are seemingly immune to this sort of transformation and feel fundamentally more difficult than others. Some problems feel downright impossible to solve — could this actually be the case?
In this course, we study the theory of computation, where we use mathematics to model problems of increasing complexity and study their relationships with each other. By going through this modeling process, we can:
- Deeply understand a problem and its potential corner cases.
- Prove properties of a problem, e.g., the correctness of candidate solutions.
- Reduce a problem to another problem, i.e., formally solve one problem in terms of another.
- Categorize a problem as easier or harder than another in a precise way.
By the end of the course, we will explore the limits of computation. Are there problems that are intractable in practice? Are there problems that can provably never have a solution?