Currently, our ToC (Theory of Computation) courses are designed with the following progression of topics:
- Finite automata and regular languages
- Pushdown automata and context-free languages
- Turing Machines
- Undecidability and TMs
- Complexity classes (P, NP etc.)
If one were to redesign the ToC course where TMs in #3 and #4 above would be replaced by $\lambda$-calculus how would the rest of the course look like? That is, what would we teach in place of #1 & #2 above to progressively lead to $\lambda$-calculus? Also, could there really be chapter on complexity classes with $\lambda$-calculus as THE model of computation?