# Why models of computation are primarily focused on machines?

It seems a lot of courses (like this and this) on theory/models of computation (and even formal languages) cover DFA, NDFA, PDA, and TM in the order of increasing computational power. This of course makes sense, but why aren't various other computation models included in general? For example, we could take the route from untyped lambda calculus to simply typed lambda calculus and so on with decreasing expressiveness. (I know they are detailed in PLT, but aren't they models of computation as well?)

In brief, since all the above (and a lot more) count as different models of computation with different powers, is there any specific reason, historical or else, that the machine-like models are adopted, sometimes even exclusively?

• In my experience as a student, it depends on the course whether machine models or 'derivation rule' models like $\lambda$-calculus are used. Machine models were mostly used in (elementary) theory of computation, $\lambda$-calculus and various typed extensions were introduced in a course on computer assisted proofs. I suppose covering both types of models in a single course would be too much workload with little gain. – Discrete lizard Jan 5 '18 at 14:50
• It's mainly for historical reasons. The model of computation used for analyzing algorithms, which is the RAM machine, is also missing from this list. – Yuval Filmus Jan 5 '18 at 16:26
• @YuvalFilmus very good point. TM differentiates P vs NP very well, while RAM is better for O(1), O(n), etc., but ultimately they are just different models. (To be honest, this perspective confuses me even more on what really should be taught in theory of computation, beacause algorithms now seem to be a valid subtopic as well.) – wlnirvana Jan 6 '18 at 8:01
• RAM differentiates P and NP just as well. Turing machines and the RAM model are polynomially equivalent. – Yuval Filmus Jan 6 '18 at 12:28