The Role of Theory in Computer Science - Models of Computation: Exploring the Power of Computing - page 5

1.1.2 1950s
FINITE-STATE MACHINES: Occurring in parallel with the development of languages was the
development of models for computers. The 1950s also saw the formalization of the finite-state
machine (also called the sequential machine), the sequential circuit (the concrete realization of
a sequential machine), and the pushdown automaton. Rabin and Scott pioneered the use of
analytical tools to study the capabilities and limitations of these models.
FORMAL LANGUAGES: The late 1950s and 1960s saw an explosion of research on formal lan-
guages. By 1964 the Chomsky language hierarchy, consisting of the regular, context-free,
context-sensitive, and recursively enumerable languages, was established, as was the correspon-
dence between these languages and the memory organizations of machine types recognizing
them, namely the finite-state machine, the pushdown automaton, the linear-bounded au-
tomaton, and the Turing machine. Many variants of these standard grammars, languages,
and machines were also examined.
1.1.3 1960s
COMPUTATIONAL COMPLEXITY: The 1960s also saw the laying of the foundation for compu-
tational complexity with the classification of languages and functions by Hartmanis, Lewis,
and Stearns and others of the time and space needed to compute them. Hierarchies of prob-
lems were identified and speed-up and gap theorems established. This area was to flower and
lead to many important discoveries, including that by Cook (and independently Levin) of
NP -complete languages, languages associated with many hard combinatorial and optimiza-
tion problems, including the Traveling Salesperson problem, the problem of determining the
shortest tour of cities for which all intercity distances are given. Karp was instrumental in
demonstrating the importance of NP -complete languages. Because problems whose running
time is exponential are considered intractable, it is very important to know whether a string in
NP -complete languages can be recognized in a time polynomial in their length. This is called
the P = NP problem, where P is the class of deterministic polynomial-time languages. The
P -complete languages were also identified in the 1970s; these are the hardest languages in P to
recognize on parallel machines.
1.1.4 1970s
COMPUTATION TIME AND CIRCUIT COMPLEXITY: In the early 1970s the connection between
computation time on Turing machines and circuit complexity was established, thereby giving
the study of circuits renewed importance and offering the hope that the P = NP problem
could be resolved via circuit complexity.
PROGRAMMING LANGUAGE SEMANTICS: The 1970s were a very productive period for formal
methods in the study of programs and languages. The area of programming language seman-
tics was very active; models and denotations were developed to give meaning to the phrase
“programming language,” thereby putting language development on a solid footing. Formal
methods for ensuring the correctness of programs were also developed and applied to program
development. The 1970s also saw the emergence of the relational database model and the