Thursday, December 12, 2019

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

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


(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.


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.


CMU:                                          Great Ideas in Theoretical Computer Science

UCLouvain (Belgium)                Calculabilite (Computability)

Moscow Inst. of  Phy. and Tech.: Mathematical logic and Theory of Algorithms

Portland State University:            Computational Structures

Germany:                                     Informatik 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.


  1. Models of Computation sounds like you spend a whole semester talking about stuff like Wang tiles and membrane computing.

    1. I would have absolutely taken that course as an elective if it existed.

  2. To me, Models of Computation sound more like what "Structure and Interpretation of Computer Programs" is about. I.e. lazy vs eager evaluation, prolog, language design, circuit design, etc...

  3. The problem with cryptography is that there are at least two cryptographies.

    One is about one-way functions and random number generators; the other one is about RSA and CBC cyphers.

  4. Why is “Great Ideas in Theoretical Computer Science?” too narrow?

    At Harvard I changed the name of the course from “Introduction to the theory of computing” to “introduction to theoretical computer science” because I thought the latter term is broader and hints at topics such as cryptography, randomness in computation, and quantum computing that intersect with computational complexity but are not a subset of it.

    1. Good Point.
      Actually `Great ideas' sounds like a Great course, but is to wide a name to be a good universal name for a DFA and/or CFG and/or... course I am talking about.

  5. On a related note: the ACT of SIGACT *used* to stand for "Automata and Computability Theory" and now stands for "Algorithms and Computation Theory".

    The different titles are really a function of the starting point and content for the course (as well as inertia) not some lack of consensus on what to call the same material.

    Some of the big differences:

    - Does the course have a large focus on finite state machines/grammars/PDAs, along with computability?

    If so, you will tend to have the "formal languages/automata" or MAYBE "theory of computation", but maybe only if the course extends into complexity.

    - Does the course have a significant focus on computability?

    If so, "Theory of Computing/Computation Theory/Theory of Computation" seem appropriate.

    - Course titles like "Great Ideas in TCS" and "Intro to Theoretical Computer Science" suggest that the material covers substantial algorithmic content as well. The idea is fine, but I think it is another apples and oranges comparison.

  6. Just posed this question to a coworker who went to UCF. Apparently these topics are spread out among the "Discrete Structures" (discrete math) ugrad courses there, with most of it concentrated in Discrete Structures II. That's about as informative a course title as "Informatik III", if not less so.

    1. My coworker texted me later to mention that the two Discrete Structures courses are commonly referred to by the student body as "Little Discrete" and "Big Discrete".

  7. Bill, I doubt that Informatak is a term. please check and get back to me. did you mean informatik ? If so, make correction.

  8. Was a your spell-checker that turned Calculabilité (perfectly good French) into Calulabitite (huh?)? What algorithm was it using?

    1. The algorithm was `me copying a comment from the last post' which is, as evidenced from your correction and the last comment, not a prefect algorithm. I have fixed it.