2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Discrete lizard ♦
    Jan 5, 2018 at 14:50
  • 2
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Jan 5, 2018 at 16:26
  • $\begingroup$ @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.) $\endgroup$
    – wlnirvana
    Jan 6, 2018 at 8:01
  • 1
    $\begingroup$ RAM differentiates P and NP just as well. Turing machines and the RAM model are polynomially equivalent. $\endgroup$
    – Yuval Filmus
    Jan 6, 2018 at 12:28

1 Answer 1

Reset to default
5
$\begingroup$

I suspect that there are two reasons:

  • Historical reasons. This is how we've always done it. Academia can be slow to change. Also, machines provide a platform for studying concepts like the power of non-determinism. We don't know how to fully understand the power of non-determinism when considering realistic models of computation (for instance, we haven't resolved the P vs NP question), but when we look at more limited models of computation, it's possible to fully work out the power of nondeterminism. So, this gives us a platform for understanding some interesting concepts about computation.

  • Pragmatic reasons. DFAs, NDFAs, and PDAs are useful and important to understand if you want to build a lexer or parser, so they're very useful when building compilers. A few decades ago, this was a powerful motivation for studying the subject: here is a practical need (how do we structure the front-end of a compiler?) and one where there is some beautiful theory that is directly applicable. Thus, such a course might gain support both from theoreticians who are most interested in the theory, and from compilers folks who are motivated by practical concerns. It's not clear that this is still the most important thing for students to learn these days -- today, how many students are ever going to need to write a lexer or parser for a compiler? -- but academic courses are slow to change.

I'm not trying to argue this is the only reasonable way to do it. A course on variants of the lambda calculus might be quite interesting, too. But I suspect these factors might partly explain why such courses are common.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.