| | | Course Goals |
This course seeks to develop some of the fundamental theoretical ideas underlying the notion of computation. Two basic abstractions form the core of computation: the encoding of computational problems as languages (collections of strings), and the mathematical modeling of real-world, programmable computers as finite-state automata that take strings as inputs and produce strings as output.
We will study a fairly broad array of topics in this course, including finite state automata and regular languages, pushdown automata and context-free languages, Turing machines, and decidable and undecidable problems.
| | | Course Goals |