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

1.1 A Brief History of Theoretical Computer Science
Theoretical computer science uses models and analysis to study computers and computation.
It thus encompasses the many areas of computer science sufficiently well developed to have
models and methods of analysis. This includes most areas of the field.
1.1.1 Early Years
TURING AND CHURCH: Theoretical computer science emerged primarily from the work of
Alan Turing and Alonzo Church in 1936, although many others, such as Russell, Hilbert, and
Boole, were important precursors. Turing and Church introduced formal computational mod-
els (the Turing machine and lambda calculus), showed that some well-stated computational
problems have no solution, and demonstrated the existence of universal computing machines,
machines capable of simulating every other machine of their type.
Turing and Church were logicians; their work reflected the concerns of mathematical logic.
The origins of computers predate them by centuries, going back at least as far as the abacus, if
we call any mechanical aid to computation a computer. A very important contribution to the
study of computers was made by Charles Babbage, who in 1836 completed the design of his
first programmable Analytical Engine, a mechanical computer capable of arithmetic operations
under the control of a sequence of punched cards (an idea borrowed from the Jacquard loom).
A notable development in the history of computers, but one of less significance, was the 1938
demonstration by Claude Shannon that Boolean algebra could be used to explain the operation
of relay circuits, a form of electromechanical computer. He was later to develop his profound
“mathematical theory of communication” in 1948 as well as to lay the foundations for the
study of circuit complexity in 1949.
FIRST COMPUTERS: In 1941 Konrad Zuse built the Z3, the first general-purpose program-
controlled computer, a machine constructed from electromagnetic relays. The Z3 read pro-
grams from a punched paper tape. In the mid-1940s the first programmable electronic com-
puter (using vacuum tubes), the ENIAC, was developed by Eckert and Mauchly. Von Neu-
mann, in a very influential paper, codified the model that now carries his name. With the
invention of the transistor in 1947, electronic computers were to become much smaller and
more powerful than the 30-ton ENIAC. The microminiaturization of transistors continues
today to produce computers of ever-increasing computing power in ever-shrinking packages.
EARLY LANGUAGE DEVELOPMENT: The first computers were very difficult to program (cables
were plugged and unplugged on the ENIAC). Later, programmers supplied commands by
typing in sequences of 0's and 1's, the machine language of computers. A major contribution
of the 1950s was the development of programming languages, such as FORTRAN, COBOL,
and LISP. These languages allowed programmers to specify commands in mnemonic code and
with high level constructs such as loops, arrays, and procedures.
As languages were developed, it became important to understand their expressiveness as
well as the characteristics of the simplest computers that could translate them into machine
language. As a consequence, formal languages and the automata that recognize them became
an important topic of study in the 1950s. Nondeterministic models - models that may have
more than one possible next state for the current state and input - were introduced during this
time as a way to classify languages.