Why is there no all-encompassing term for a course on Models of Computation?

Computational Complexity 2019-12-12

In my last blog post I asked my readers to leave comments saying what the name of the course that has some of Regular Languages, Context Free Languages  Decideability, P, NP (any maybe other stuff) in it.  I suspected there would be many different names and their were. I was able to put all but 6 into 4 equivalence classes. So that's 10 names. Thats a lot  especially compared to (Introduction to) Algorithms and (Introduction to) Cryptography which I suspect have far fewer names. One commenter pointed out that the reason for the many different names is that there are many versions of the course. That's not quite an explanation since there are also many different versions of Cryptography---at UMCP  crypto is cross listed in THREE departments (CS, Math, EE) and its taught by 6 or so different people who don't talk to each other (I am one of them). I think Algorithms is more uniform across colleges. I think that terms Algorithms and Cryptography are both rather broad and can accommodate many versions of the courses, whereas no term seems to be agreed upon to encompass the DFA etc course. Even saying DFA etc is not quite right since some of the courses spend little or even no time on DFA's. Below is a list of all the names I got and some comments. Note that some schools appear twice since they have two courses along these lines. ----------------------------------------- TITLE: (Introduction to) Theory of Computation: Swarthmore:                                            Theory of Computation UCSD:                                                     Theory of Computation Saint Michaels:                                        Theory of Computation Univ of Washington: Introduction to the Theory of Computation Waterloo:                  Introduction to the Theory of Computing COMMENT: Theory of Computation could have been the term that encompasses all of these courses. I speculate that it didn't catch on since it sounds too much like computability theory which is only one part of the course. ------------------------ TITLE: Formal Languages and XXX CMU:                                                Formal Languages, Automata, and Computability Florida Tech:                                    Formal Languages and Automata Theory UC-Irvine:                                        Formal Languages and Automata Theory Univ of Chicago:    Introduction to Formal Languages University of Bucharest:                 Formal Language and Automata TU Darmstadt:                                Formal Foundations of CS I: Automata, Formal Languages, and Decidability TUK Germany:                               Formal Languages and Computability COMMENT: The title makes it sound like they don't cover P and NP. I do not know if thats true; however, I speculate that, it could never be the encompassing term. Spell Check things Automata and Computability are not words, but I've googled them and they seem to be words. -------------------------- TITLE: Computability/Decidability and Complexity/Intractability Reed College: Computability and Complexity Caltech:          Decidability and Intractability COMMENT: The title makes it sound like they don't cover regular or context free languages. I do not know if that's true; however, I speculate that, since the terms sound that way, they never caught on as the general term. Spellecheck thinks that neither Decidability nor Decideability is a word. Google seems to say that I should leave out the e, so I will. ------------------------------ TITLE:  Blah MODELS Blah Tel-Aviv (a long time ago) Computational Models UIUC:                               Algorithms and Models of Computation (also has some algorithms in it) Waterloo:                                                   Models of Computation (enriched version) COMMENT: Models of Computation sounds like a good name for the course! Too bad it didn't catch on.  It would also be able to withstand changes in the content like more on parallelism or more on communication complexity. ------------------------------ TITLE: MISC CMU:                                          Great Ideas in Theoretical Computer Science UCLouvain (Belgium)                Calulabitite (Computability) Moscow Inst. of  Phy. and Tech.: Mathematical logic and Theory of Algorithms Portland State University:            Computational Structures Germany:                                     Informatak III (Not all of Germany) Univ of Chicago:                         Introduction to Complexity COMMENT: All of these terms are to narrow to have served as a general term.