How would a theory of computation course that culminated in lambda-calculus as "the" model of computation, instead of Turing machines, look like? 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 &amp; #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?
The kind of approach to theory of computation you describe is what I like to call an abstract machine based computability theory:
i.e. a theory that define computable functions/languages/etc via some abstract kind of machine (automata, linear automata, Turing
machine etc).

An approach that uses $\lambda$-calculus instead of Turing machines could be thought as an expressions based computability theory:
i.e. a theory where one prescribe some basic operations which are intuitively calculable and some operators defined between them to
build other computable operations.

In this expression based computability theory


regular expressions correspond to finite state automata;                                                                             
linear and context free grammar correspond to pushdown automaton and linear bounded automaton
(untyped) $\lambda$-calculus correspond to Turing machines
I don't know very much about complexity in $\lambda$-calculus but I guess  it could be approached as done for complexity of $\mu$-recursive function or of logic formulas, classifying $\lambda$-terms in complexity
classes by their structure (then of course it would be nice to compare these complexity classes with complexity classes for other models of computation, like Turing machines).


Hope this helps.