In lieu of an abstract, here is a brief excerpt of the content:

  • Machines, Languages, and Computation at MIT
  • Peter J. Denning (bio), Jack B. Dennis (bio), and David Walden

Once upon a time, there was a course at MIT in the Electrical Engineering and Computer Science department called 6.253, Theoretical Models of Computation. It was developed in the time when computer science was not such a large field and all computer scientists were expected to know everything, including theory, programming, architecture, and systems. Rivalries between different parts of the field were just starting to appear.

In the mid-1960s, a tremendous outpouring of new insights from Noam Chomsky and his students in the Department of Linguistics occurred at MIT. They were uncovering unsuspected relationships between formal languages and automata. In particular, they proposed that each category of automata—finite state, push-down, linear-bounded, and Turing machines—could be characterized by the classes of languages they could recognize. They found that each class of language could be described by the structure of formal grammar needed to define it. They also found that they could construct automata from the grammars and grammars from automata. For example, a language would be classified as pushdown-recognizable if a pushdown automaton could tell whether a given input string is in the language. A context-free grammar could be converted to a description of a pushdown automaton for recognizing a language, and a context-free grammar could be constructed from a pushdown automaton. These insights were extremely valuable in the construction of compilers for higher-level language such as Algol.

Jack Dennis was a faculty member in the Laboratory for Computer Science at the time that Chomsky’s students were presenting their results at seminars. He became convinced that it was important for computer scientists to learn this perspective. At that time, the only related books were Marvin Minsky’s course notes, which were eventually published by Prentice Hall,1 and several books on switching theory and logic circuits. These books did not take the view that the automata they discussed were language recognizers. That omission was Jack’s motivation for creating the course 6.253. David Kuck and he designed the course and taught it together in the spring of 1965. Peter Denning joined him as a teaching assistant in 1966 and soon became a full partner in refining and extending the notes, developing problem sets, and lecturing.

In 1967, the computer science editor of Prentice Hall, John Davis, found out about the notes for 6.253 and persuaded us (Jack and Peter) to make a book from them. At the time, we envisioned that we could complete the manuscript in 1968. Unfortunately, that did not come to be. Peter was writing his PhD thesis in 1968 and then he joined the electrical engineering faculty at Princeton. Jack found that members of the theory section of the Lab for Computer Science could not accept that a couple of systems guys would teach a good course and write a good book on a formal topic. We were not card-carrying theorists! Because he wanted to devote himself to developing a course on computer systems (numbered 6.232), Jack recruited Joseph Qualitz to take over 6.253 after Peter left. Joe kept the course going and helped complete the book project. The 6.253 course was taught for last time in the fall of 1973.

With all the distractions, and our reduced involvement in teaching the course, it took us 10 years to complete the book. Machines, Languages, and Computation (MLC) was published in 1978, a decade later than we had originally estimated.2

At Princeton, Peter encountered a similar reaction from the theorists as Jack had at MIT. Princeton had some of computer science’s greatest theorists either on the faculty (Jeff Ullman) or closely affiliated (Al Aho and John Hopcroft). Hopcroft and Ullman were working on their own book about automata and languages, which was published in 1979.3 Peter taught a few sections of the automata theory course from the draft of his MLC book. But the Hopcroft-Ullman book was more popular among the Princeton faculty and students. Jeff and Peter had frequent conversations about the formulation of the MLC book. Jeff liked...

pdf

Share