Princeton University

In a discussion on the last day of the second NATO Conference on
Software Engineering held in Rome in October 1969, Christopher
Strachey, Director of the Programming Research Group at Oxford
University, lamented that "one of the difficulties about computing
science at the moment is that it can't demonstrate any of the things
that it has in mind; it can't demonstrate to the software engineering
people on a sufficiently large scale that what it is doing is of
interest or importance to them."^{(2)} As
example he cited the general ignorance or neglect by industry of the
recursive methods that computer scientists took to be fundamental to
programming. Blaming industry for failing to support research and
faulting theorists for neglecting the real problems of practitioners,
he went on to explore how the two sides might move closer together.

Strachey's prescription is of less concern here than his diagnosis,
which points to an interesting case study in the relation of science to
technology in a field thought to be mathematical at heart. His remarks
came at a significant point in the history of computing. It marked the
end of two decades during which the computer and computing acquired
their modern shape. As the title of a recent book on the early computer
industry suggests, it was a time of *Creating the Computer*,
when the question, "What is a computer, or what should it be?", had no
clear-cut answer.^{(3)} By the late 1960s,
the main points of that answer had emerged, determined as much in the
marketplace as in the laboratory. At the same time, a consensus began
to form concerning the nature of computer science, at least among those
who believed the science should be mathematical.^{(4)}
That consensus, reflected in the new category of "computer science"
added to *Mathematical Reviews* in 1970, rested in part on
theory and in part on experience, if not of the marketplace directly,
then of actual machines applied to actual problems.^{(5)}

As the computer was being created, then, so too was the mathematics of computing. When we think of the computer as a machine, it is not surprising that it should be an object of design, where available means and chosen purposes must converge on effective action. We are less accustomed to the idea that a mathematical subject might be a matter of design, that is, the matching of means to ends that themselves are open to choice. Yet, the agenda of the mathematical theory of computation changed as computers and programs grew in size and complexity during the first twenty years. If, as Saunders MacLane has said, mathematics is "finding the form to fit the problem", the mathematics of computing began with a search for the problem. Different people made different choices about what was significant, and the mathematics on which they drew varied accordingly. What follows is a first reconnaissance over this shifting terrain.

The electronic digital stored-program computer emerged from the
convergence of two separate lines of development each stretching back
over several centuries but generally associated with the names of
Charles Babbage and George Boole in the mid-19th century.^{(6)}
The first was concerned with mechanical calculation, the second
involved mathematics and logic. In coming together, they brought two
models of computation: the Boolean algebra of circuits created by
Claude Shannon in 1938 and the mathematical logic of Turing machines
devised by Alan Turing in 1936. In the early '50s, the new field of
automata theory, inspired a decade earlier by the idea of the nervous
system as a switching circuit and recently reinforced by the notion of
the brain as computer, encompassed the two models at opposite ends of a
spectrum ranging from finite deterministic machines to infinite or
growing indeterministic machines.^{(7)}

At the one end, beginning with the work of David A. Huffman, E.F.
Moore, and G.H. Mealy, switching theory broadened its mathematical
scope beyond Boolean algebra by gradually shifting attention from the
internal structure of finite-state machines to the patterns of input
they can recognize and thus to the notion of a machine as a mapping or
partition of semigroups. By 1964, the field of algebraic machine theory
was well established, with close links to the emerging fields that were
reconstituting universal algebra.^{(8)} At
the other end of the spectrum, during the mid-'60s Turing machines of
various types became the generally accepted model for measuring the
complexity of computations, a question that shifted attention from
decidability to tractability and enabled a classification of problems
in terms of the computing resources required for their solution. First
broached by Michael O. Rabin in 1959 and '60, the subject emerged as a
distinct field with the work of Juris Hartmanis and Richard E. Stearns
in 1965 and acquired its full form with the work of Steven Cook and
Richard Karp in the early '70s.^{(9)} The
field has formed common ground for computer science and operations
research, especially in the design and analysis of algorithms.

As the two historical models of computation developed during the 1950s and '60s, they retained their distinctive characteristics. The one stayed close to the physical circuitry of computers, analyzing computation as it went on at the level of the switches. The other stood far away, considering what can be computed in the abstract, irrespective of the particular computer employed. By the mid-50s, however, a new --and, to some extent, unanticipated-- complex of questions had arisen in the middle of these extremes. Programming was becoming an activity in its own right, prompting the development of programming languages and compiling techniques to ease the task of writing instructions for specific machines and to make programs transferable from one machine to another. The then dominant application to numerical analysis meant that most such languages would have a mathematical appearance, and the orientation to the programmer meant that they would use symbolic language. But some languages were aimed at insight into computing itself, and they emphasized the manipulation of symbols as opposed to numerical computation.

The explosion of languages over the decade 1955-65, accompanied by the development of general techniques for their implementation and leading to programs of ever greater size and complexity, established all these things as matters of practical fact. In doing so, they challenged computer scientists to give a mathematical account of them. The challenge grew increasingly urgent as problems of cost, reliability, and managerial control multiplied. The call for a discipline of "software engineering" in 1967 meant to some the reduction of programming to a field of applied mathematics.

At the same time, it was unclear what mathematics was to be applied
and where. At first, automata theory seemed to hold great promise. In
1959, building on Stephen Kleene's general characterization of the
events that prompt a response from the nerve nets specified by Warren
McCulloch and Walter Pitts, Michael Rabin and Dana Scott showed that
finite automata defined in the manner of Moore machines accepted the
same "regular" sequences of characters (which corresponded to free
semigroups) and extended the result to nondeterministic and other
finite automata.^{(10)} Such regular
expressions constituted the first of Noam Chomsky's hierarchy of phrase
structure grammars, the fourth and highest of which corresponded to
Turing machines. The suggested link between automata and mathematical
linguistics, with its potential application to machine translation,
sparked a burst of research. The early '60s saw the creation of
pushdown and linear-bounded automata to correspond to the intermediate
levels of context-free and context-sensitive grammars. In 1965 formal
language theory emerged as a field of computer science independent of
the mathematical linguistics from which it had sprung.^{(11)}
The new field provided a mathematical basis for lexical analysis and
parsing of languages and thus gave theoretical confirmation to
techniques such as John Backus' BNF, developed independently for
specifying the syntax of Algol.

Even as that work was going on, some writers began to argue that
automata theory would not suffice as a mathematical theory of
computation.^{(12)} In principle, the
computer was a finite state machine; in practice it was an intractably
large finite state machine. Moreover, it was not enough to know that a
program is syntactically correct. A program is a function that maps
input values to output values and hence is a mathematical object, the
structure of which should itself be accessible to expression and
analysis. Moreover, programs written in programming languages run on
machines and must be translated by means of compilers into the
languages of those machines. Both the functional structure of the
program and its translation are a matter of semantics, a matter of what
the statements of the program, and hence the program itself, mean.
Three approaches to semantics emerged in the mid-'60s. The operational
approach took the compiler itself to constitute a definition of the
semantics of the language for a given machine, thus leaving open the
question of establishing the equivalence of two compilers. The
deductive approach, introduced by R.W. Floyd in 1967, linked logical
statements to the steps of the program, thereby specifying its behavior
as well as providing a means of verifying the program.^{(13)}
Mathematical semantics aimed at a formal theory that would serve as a
means of specification for compilers and as a metalanguage for talking
about programs, algorithms and data.

The proposal to make semantics the basis of a mathematical theory
of computation came from two sources with different, though
complementary emphases. John McCarthy was concerned with the structure
of algorithms and how they might be compared with one another.
Christopher Strachey spoke about the structure of computer memory and
how programs alter its contents. Both men found common ground in a
system of functional notation, the lambda calculus, first introduced by
Alonzo Church in the early 1930s but subsequently abandoned by him when
it did not fulfill his hopes of its serving as a foundation for
mathematical logic.^{(14)} The use of the
lambda calculus as a metalanguage for programs led to the first
construction of a mathematical model for it, and it has subsequently
come to be viewed as the "pure" programming language. None of this
proceeded smoothly or directly, and it is worth looking at it in a bit
more detail.

At the Western Joint Computer Conference in May 1961, McCarthy
proposed "A Basis for a Mathematical Theory of Computation".^{(15)} "Computation is sure to become one
of the most important of the sciences," he began,

This is because it is the science of how machines can be made to carry out intellectual processes. We know that any intellectual process that can be carried out mechanically can be performed by a general purpose digital computer. Moreover, the limitations on what we have been able to make computers do so far clearly come far more from our weakness as programmers than from the intrinsic limitations of the machines. We hope that these limitations can be greatly reduced by developing a mathematical science of computation.McCarthy made clear what he expected from a suitable theory: first, a universal programming language along the lines of Algol but with richer data descriptions; second, a theory of the equivalence of computational processes, by which equivalence-preserving transformations would allow a choice of among various forms of an algorithm, adapted to particular circumstances; third, a form of symbolic representation of algorithms that could accommodate significant changes in behavior by simple changes in the symbolic expressions; fourth, a formal way of representing computers along with computation; and finally a quantitative theory of computation along the lines of Shannon's measure of information.^{(16)}

McCarthy did not pretend to have met any of these goals, which spanned a broad range of currently separate areas of research. His work on the programming language LISP, however, had suggested a system of formalisms that allowed him to prove the equivalence of computations expressed in them. The formalisms offered means of describing functions computable in terms of base functions, using conditional expressions and recursive definitions. They included computable functionals (functions with functions as arguments), non-computable functions (quantified computable functions), ambiguous functions, and the definition both of new data spaces in terms of base spaces and of functions on those spaces, a feature that Algol, then the most theoretically oriented language, lacked. The system constituted the first part of McCarthy's paper; the second part set out some of its mathematical properties, a method called "recursion induction" for proving equivalence, and a comparison of his system with others in recursive function theory and programming.

In his first presentation of his system in 1960, McCarthy had used
a variation of LISP as a metalanguage.^{(17)}
He then introduced the lambda calculus, to which he had earlier turned
when seeking a notation that allowed the distribution of a function
over a list with an indeterminate number of arguments.^{(18)}
Concerned primarily with LISP as a working language and satisfied with
its metatheoretical qualities, McCarthy did not pursue the further
reduction of LISP to the lambda calculus; indeed, he adopted Nathaniel
Rochester's concept of *label* as a means of circumventing both
the complicated expression and the self-applicative function required
by recursive definition in the pure notation. Others, most notably
Peter J. Landin, did look to the lambda calculus itself as a
metalanguage for programs, seeing several advantages in it.^{(19)} It made the scope of bound variables
explicit and thus prevented clashes of scope during substitution (that
is one reason why Church designed it). Its rules and procedures for
reduction to normal form made it possible to show that two different
expressions were equivalent in the sense of having the same result when
applied to the same arguments. Moreover, it was type-free, treating
variables and functions as equally abstractable entities.

The first property clarified the complexities of evaluating the
arguments of a function when their variables have the same name as
those of the function.^{(20)} The second
property provided analytical insight into the structure of functions,
showing how they were constructed from basic functions and allowing
transformations among them. In McCarthy's system, it underlay the
technique of recursive induction. For example, let integer addition be
defined recursively by the conditional equation *m* + *n*
= (*n* = 0 --> *m*, T --> *m*' + *n*^{-}),
where *m*' is the successor of *m* and *n*^{-}
is the predecessor of *n*.^{(21)}
To show that (*m* + *n*)' = *m*' + *n*,
let *g*(*m*,*n*) = (*m* + *n*)' = (*n*
= 0 --> *m*, T --> *m*' + *n*^{-})'
= (*n* = 0 --> *m*', T --> (*m*' + *n*^{-})')
= (*n* = 0 --> *m*', T --> *g*(*m*',*n*^{-})),
and *h*(*m*,*n*) = *m*' + *n* = (*n*
= 0 --> *m*', T --> (*m*')' + *n*^{-})
= (*n* = 0 --> *m*', T --> *h*(*m*',*n*^{-})).
Whence *g* and *h* both satisfy the relation *f*
= λ*m*.λ*n*.(*n* = 0 --> *m*', T -->
*f*(*m*',*n*^{-})) when substituted for *f*
and hence are equal.^{(22)}

The third property opened a link to the particular nature of the stored-program computer and thus fitted McCarthy's rephrasing of his expectations in a second paper, "Towards a Mathematical Science of Computation", delivered at IFIP 62. The entities of computer science consist of "problems, procedures, data spaces, programs representing procedures in particular programming languages, and computers." Once distinguished from problems, defined by the criteria of their solution, the construction of complex procedures from elementary ones could be understood in terms of the well established theory of computable functions. However, there was no comparable theory of the representable data spaces on which those procedures operate. Similarly, while the syntax of programming languages had been formalized, their semantics remained to be studied. Finally, despite the fact that computers are finite automata, "Computer science must study the various ways elements of data spaces are represented in the memory of the computer and how procedures are represented by computer programs. From this point of view, most of the current work on automata theory is beside the point."

McCarthy did not persuade many of his leading American colleagues,
who doubted the need for, and feasibility of, a formal semantics, but
on this last point he found an ally in Strachey, for whom Landin had
been working and who built his contribution to the 1964 Working
Conference on Formal Description Languages in Vienna precisely on the
question of what goes on in the memory (store) of a computer and on the
"essentially computer-oriented" operations of assignment and transfers
of control that go on there. In "Toward a Formal Semantics", Strachey
worked from the model of a computer's memory as a finite set of *N*
objects, well ordered in some way by a mapping that assigns to each of
them a *name*, or *L-value*. Each object is itself a
binary array, which may be viewed as the *value*, or *R-value*
associated with the name. A program consists of a sequence of
operations applied to names and values to produce values associated
with names; in other words, a mapping of names and values into names
and values. However the operations are defined abstractly, they reduce
to the instruction set of the processor. In principle, one should be
able to treat a program as a mathematical object and analyze its
structure.

That structure cannot be entirely abstract or syntactical, at least
not if it is to meet the most basic requirements of real programming.
As an analysis of the assignment command shows, it is necessary to
distinguish between the *L-value* and *R-value* of an
expression. That is, the command ε_{1} := ε_{2}
requires that the expression on the left be interpreted as a name and
that on the right as a value; the two expressions require different
evaluations. While one could make that evaluation trivial by
restricting the command to allow only primitive names on the left,
doing so would sacrifice such features as list-processing in LISP and
Strachey's own CPL. Moreover, the value of a name may extend beyond a
binary array to include an area of memory, as in the case, peculiar to
the stored-program computer, where it contains executable code. Thus,
expressions such as "(if *x* > 0 then *sin* else *cos*)(*x*)",
meaningless to the mathematical eye, make sense computationally: the
variable *x* and the procedures for *sin* and *cos*
are equally valid values of their names.

To capture the structure of this model of memory, Strachey
introduced two operators, "loading" and "updating", which retrieve and
store the *R-values* associated with *L-values*.
Symbolically, let α denote an *L-value* and β its associated *R-value*,
and let σ denote the "content of the store" or the total set of *R-values*
at any given moment. Then "loading", denoted by *C*, will be a
function of α, which when applied to σ yields β, that is, β = (*C*(α))(σ).
"Updating", denoted *U*, produces a new content ' through the
operation (*U*(α))(β',σ), where β' is a value compatible with β.
Hence, if one treats the "natural" result of an expression ε as its *L-value*,
expressed symbolically as α = *L*(ε,σ), then its *R-value*
can be obtained by means of the loading operator: β = *R*(ε,σ)
= (*C*(*L*(ε,σ)))(σ). Introduced as functions into the
descriptive expressions of a language, Strachey argued, these operators
provided a specification of how the results of the expressions should
be treated at the level of the computer.

Drawing on Landin's work, Strachey embedded the *L* and *R*
functions into the λ-calculus, which he and his collaborators used as a
metalanguage for specifying and analyzing the semantics of programming
languages.^{(23)} Although they called the
enterprise mathematical, it had no underlying mathematical structure to
serve as model for the formal system. As Scott insisted when he and
Strachey met in Vienna in 1968, their analysis amounted to no more than
a translation of the object language into the metalanguage. How the
data types and functions of the language were to be constructed
mathematically remained an open question. Scott's criticism of Strachey
echoed Anil Nerode's reaction to McCarthy's approach.^{(24)}
There was no mathematics in it.

Scott had been working in various areas of logic during the '60s,
having concluded that none of the areas of theoretical computer science
was heading in promising directions.^{(25)}
He had gradually formed his own idea of where and how the mathematics
entered the picture. He sought the middle ground in the tension
inherent in applied mathematics. The mathematics moves in the direction
of ever-greater abstraction from the intended application. Yet, the
application sets the conditions for the abstraction. The mathematical
model must maintain contact with the physical model. The test of
practicality always looms over the effort. A mathematical theory of
computation addressed to understanding programs has to connect the
abstract model to the concrete machine, Scott argued in 1970: "... an *adequate*
theory of computation must not only provide the abstractions (what is
computable) but also their 'physical' realizations (how to compute
them)."^{(26)} The means of realization
had been known for some time, he added; what was needed were the
abstractions, which could expose the structure of a programming
language. "Now it is often suggested that the meaning of the language
resides in one particular compiler for it. But that idea is wrong: the
'same' language can have many 'different' compilers. The person who
wrote one of these compilers obviously had a (hopefully) clear
understanding of the language to guide him, and it is the purpose of
mathematical semantics to make this understanding 'visible'. This
visibility is be achieved by abstracting the central ideas into
mathematical entities, which can then be 'manipulated' in the familiar
mathematical manner."^{(27)}

The mathematical entities derived from the physical structure of
the computer. Mathematical semantics concerned *data types* and
the *functions* that map them from one to another. The spaces
of those functions also form data types. The finite structure of the
computer means that some finite *approximation* is needed for
functions, which are by nature infinite objects (e.g. mappings of
integers to integers). Because computers store programs and data in the
same memory, programming languages allowed unrestricted procedures
which could have unrestricted procedures as values; in particular a
procedure could be applied to itself. "To date," Scott claimed,

no mathematical theory of functions has ever been able to supply conveniently such a free-wheeling notion of function except at the cost of being inconsistent. The mainOne did not need unrestricted procedures to appreciate the problems posed by the self-application facilitated by the design of the computer. Following Strachey, consider the structure of computer memory, representing it mathematically as a mapping of contents to locations. That is, state σ is a function mapping each elementmathematicalnovelty of the present study is the creation of a proper mathematical theory of functions which accomplishes these aims (consistently!) and which can be used as the basis for themetamathematicalproject of providing the "correct" approach to semantics.

Recent work on interval arithmetic suggested that one might seek justification through a partial ordering of data types and their functions based on the notion of "approximation" or "informational content". With the addition of an undefined element as "worst approximation" or "containing no information", the data types formed a complete lattice, and monotonic functions of them preserved the lattice. They also preserved the limits of sequences of partially ordered data types and hence were continuous. Scott showed that the least upper bound of the lattice, considered as the limit of sequences, was therefore the least fixed point of the function and was determined by the fixed point operator of the λ-calculus. Hence self-applicative functions of the sort needed for computers had a consistent mathematical model. And so too, by the way, did the λ-calculus for the first time in its history.

Scott's lattice-theoretical model established a rigorous
mathematical foundation for the program Strachey had proposed in 1964.
Together they wrote "Toward a Mathematical Semantics for Computer
Languages", which "covers much the same ground as Strachey ["Toward a
Formal Semantics"], but this time the mathematical foundations are
secure. It is also intended to act as a bridge between the formal
mathematical foundations and their application to programming languages
by explaining in some detail the notation and techniques we have found
to be most useful."^{(29)} Mathematical
semantics formed another sort of bridge as well. It led back to the
body of algebraic structures that had provided previous models of
computing, but it now spanned the gap between finite-state machines and
Turing machines (in the equivalent form of the lambda calculus) by
taking account of the random-access, stored program device that
embodied them both.

By 1970 computer science had assumed a shape recognized by both the mathematical and the computing communities, and it could point to both applications and mathematical elegance. Yet, it took the form more of a family of loosely related research agendas than of a coherent general theory validated by empirical results. So far, no one mathematical model had proved adequate to the diversity of computing, and the different models were not related in any effective way. What mathematics one used depended on what questions one was asking, and for some questions no mathematics could account in theory for what computing was accomplishing in practice.

In 1969, Christopher Strachey indicated the problem confronting
those who looked to computer science for help in addressing the
problems of productivity and reliability in the software industry.
About a decade later, a committee in the United States reviewing the
state of art in theoretical computer science echoed his diagnosis,
noting the still limited application of theory to practice.^{(30)} For all the depth of results in
computational complexity, "the complexity of most computational tasks
we are familiar with -- such as sorting, multiplying integers or
matrices, or finding shortest paths -- is still unknown." Despite the
close ties between mathematics and language theory, "by and large, the
more mathematical aspects of language theory have not been applied in
practice. Their greatest potential service is probably pedagogic, in
codifying and given clear economical form to key ideas for handling
formal languages." Efforts to bring mathematical rigor to programming
quickly reached a level of complexity that made the techniques of
verification subject to the very concerns that prompted their
development. Mathematical semantics could show "precisely why [a] nasty
surprise can arise from a seemingly well-designed programming
language", but not how to eliminate the problems from the outset. As a
design tool, mathematical semantics was still far from the goal of
correcting the anomalies that gave rise to errors in real programming
languages.

Another decade later, his successor in the Chair of Computation at
Oxford, C.A.R. Hoare, spoke of the mathematics of computing more as
aspiration than as reality.^{(31)} He held
it as a matter of principle that computers are mathematical machines,
computer programs are mathematical expressions, a programming language
is a mathematical theory, and programming is a mathematical activity.
"These are general philosophical and moral principles, and I hold them
to be self-evident -- which is just as well, because all the actual
evidence is against them. Nothing is really as I have described it,
neither computers nor programs nor programming languages nor even
programmers."

The sense of anomaly behind such evaluations becomes understandable in light of the historical precedents against which the subject was being viewed. Looking toward a mathematical theory of computation in 1962, McCarthy reached for a familiar touchstone:

In a mathematical science, it is possible to deduce from the basic assumptions, the important properties of the entities treated by the science. Thus, from Newton's law of gravitation and his laws of motion, one can deduce that the planetary orbits obey Kepler's laws.He extended the analogy at the conclusion of his 1963 article by reference to later successes in mathematical physics:^{(32)}

It is reasonable to hope that the relationship between computation and mathematical logic will be as fruitful in the next century as that between analysis and physics in the last. The development of this relationship demands a concern for both applications and mathematical elegance.In these historical instances, mathematization had elicited the essential simplicity of an apparently complex world. Newton showed that Kepler's complicated laws followed from the assumption of a simple inverse-square force working according to equally simple laws of motion, and that Galileo's laws of falling bodies could be treated as a limiting case of that model. Hence, pendulums on earth and planets in the heavens move in the same way, and the former can be used to measure the latter both intrinsically (constant of gravity) and extrinsically (marker of time). In an important sense, nineteenth-century mathematical physics merely extended the Newtonian model to other realms of the physical world, even when, as in the case of thermodynamics and electromagnetic theory, the basic laws were substantially different. Those theories tied complicated and diverse phenomena together, drawing them as consequences from a simple mathematical structure. In each case, complexity proved to be accidental, accounted for mathematically by perturbations on a basic solution; one moved from the ideal to the real by a form of analytic continuation.^{(33)}

Both theory and experience suggest that, by contrast, complexity is
an essential property of computation, to be addressed directly rather
than by degrees. Simple structures have provided understanding of
simple processes, but they have not readily compounded in any analytic
way to give an account of arbitrarily complicated processes.^{(34)} The search for a mathematical
structure of computing may well involve a new historical and
philosophical structure of mathematization.

1. Research for this paper was generously supported by the Alfred P. Sloan Foundation through its New Liberal Arts Program.

2. Peter Naur, Brian Randell, and J.N. Buxton
(eds.), *Software Engineering: Concepts and Techniques. Proceedings
of the NATO Conferences* (NY: Petrocelli, 1976), 147.

3. Kenneth Flamm, *Creating the Computer*
(Washington, DC: Brookings Institution, 1988)

4. Not all did. Several recipients of the ACM's
Turing Award addressed the question in their award lectures. Although
Marvin Minsky ("Form and content in computer science", 1969) agreed
that computers are essentially mathematical machines, he decried the
trend toward formalization and urged an experimental, programming
approach to understanding them. Allen Newell and Herbert Simon
("Computer science as empirical inquiry: Symbols and search", 1975)
took an even stronger empirical stand, arguing that computer science is
the science of computers and that the limits and possibilities of
computing could be determined only through experience in using them.
Donald E. Knuth ("Computer programming as an art", 1974) argued that
programming was irreducibly a craft skill, which would resist the
automation implicit in a mathematization of computer science. See *ACM
Turing Award Lectures. The First Twenty Years, 1966-1985* (NY: ACM
Press, 1987).

5. The new subject comprised fields taken from various headings. Programming theory, algorithms, symbolic computation, and computational complexity and efficiency had been the province of numerical analysis. From "Information and Communication" came automata theory, linguistics and formal languages, and information retrieval. To these established categories were added adaptive systems, theorem proving, artificial intelligence and pattern recognition, and simulation.

6. For a fuller sketch and further reading, see
M.S. Mahoney, "The History of Computing in the History of Technology", *Annals
of the History of Computing* (hereafter *AHC)* 10(1988),
113-25, and "Cybernetics and Information Technology", in *Companion
to the History of Modern Science*, ed. R.C. Olby *et al*.
(London/New York: Routledge, Chapman & Hall, 1989), Chap. 34

7. W.S. McCulloch and W. Pitts, "A logical
calculus of the ideas imminent in nervous activity", *Bulletin of
Mathematical Biophysics* 5(1943), 115-33. J. von Neumann, "The
general and logical theory of automata", in *Cerebral Mechanisms in
Behavior: The Hixon Symposium*, ed. L.A. Jeffries (NY: Wiley,
1951). Robert McNaughton, "The theory of automata, a survey", *Advances
in Computing* 2(1961), 379-421.

8. See, for example, J. Hartmanis and R.E.
Stearns, *Algebraic Structure of Sequential Machines*
(Englewood Cliffs, NJ: Prentice-Hall, 1966), and Paul M. Cohn, *Universal
Algebra* (Dordrecht: Reidel, 1965; 2nd rev. ed., 1981). Cf. Alfred
North Whitehead, *A Treatise of Universal Algebra* (Cambridge,
1898), I, 29: "[Boole's algebra, characterized by the relation *a*
= *a* + *a*,] leads to the simplest and most
rudimentary type of algebraic symbolism. No symbols representing number
or quantity are required in it. The interpretation of such an algebra
may be expected therefore to lead to an equally simple and fundamental
science. It will be found that the only species of this genus which at
present has been developed is the Algebra of Symbolic Logic, though
there seems no reason why other algebras of this genus should not be
developed to receive interpretations in fields of science where strict
demonstrative reasoning without relation to number or quantity is
required."

9. M.O. Rabin, "Speed of computation and
classification of recursive sets", *Third Convention of Scientific
Societies*, Israel, 1959, 1-2; "Degree of difficulty of computing a
function and a partial ordering of recursive sets", *Technical
Report No.1, ONR*, Jerusalem, 1960. J. Hartmanis and R.E. Stearns,
"On the computational complexity of algorithms", *Transactions of
the AMS* 117(1965), 285-306. S. Cook, "The complexity of theorem
proving procedures", *Proc. 3rd ACM Symposium on Theory of Computing*,
1971, 151-58. R. Karp, "Reducibility among combinatorial problems", in *Complexity
of Computer Computations* (NY: Plenum, 1972), 85-104.

10. S.C. Kleene, "Representation of events in
nerve nets and finite automata", in *Automata Studies*, ed. J.
McCarthy and C.E. Shannon (Annals of Mathematics Studies No. 34,
Princeton, 1956), 3-41. M.O. Rabin and D.S. Scott, "Finite automata and
their decision problems", *IBM Journal of Research and Development*
3(April 1959), 114-24.

11. Sheila A. Greibach, "Formal languages:
Origins and directions", *AHC* 3,1(1981), 14-41

12. For example, John McCarthy, in an article
to be discussed below, argued that none of the three current (1961)
directions of research into the mathematics of computing held much
promise of such a science. Numerical analysis was too narrowly focused.
The theory of computability set a framework into which any mathematics
of computation would have to fit, but it focused on what was unsolvable
rather than seeking positive results, and its level of description was
too general to capture actual algorithms. Finally, the theory of finite
automata, though it operated at the right level of generality, exploded
in complexity with the size of current computers. As he explained in
another article, "... [T]he fact of finiteness is used to show that the
automaton will eventually repeat a state. However, anyone who waits for
an IBM 7090 to repeat a state, solely because it is a finite automaton,
is in for a very long wait." ("Towards a mathematical science of
computation", *Proc. IFIP Congress 62* (Amsterdam:
North-Holland, 1963).

13. "Attaching Meaning to Programs", in *Mathematical
Aspects of Computer Science* (Proceedings of Symposia in Applied
Mathematics, 19; Providence: AMS, 1967), 19-32.

14. J. Barkley Rosser, "Highlights of the
history of the lambda calculus", *AHC* 6(1984), 337-49. S.C.
Kleene, "Origins of recursive function theory", *AHC* 3(1981),
52-67.

15. Reprinted, with corrections and an added
tenth section, in *Computer Programming and Formal Systems*,
ed. P. Braffort and D. Hirschberg (Amsterdam, North-Holland, 1963),
33-70.

16. *Ibid.*, 33.

17. "Recursive Functions of Symbolic Expressions and Their Computation by Machine", Communications of the ACM 3,4(1960), 184-95.

18. Interview, 3 December 1990.

19. P.J. Landin, "The mechanical evaluation of
expressions", *Computer Journal* 6(1964), 308-320.

20. McCarthy and his coworkers had encountered
this problem in designing LISP; it came to be called the FUNARG
problem. See his account in *History of Programming Languages*,
ed. R. Wexelblat (NY: Academic Press, 1981).

21. The right side of the equation is a
conditional expression, which consists of a list of conditional
propositions to be evaluated in order from left to right and which
takes the value of the consequent of the first proposition of which the
antecedent is true. In the above expression, if *n* = 0, the
value is *m*, otherwise (T is always true) it is *g*(*m*',*n*);
for example, *g*(3,2) = *g*(4,1) = *g*(5,0) =
5.

22. More precisely, in McCarthy's system, they
satisfy the relation *f* = *label*(*f*, λ*m*.λ*n*.(*n*
= 0 --> *m*', T --> *f*(*m*',*n*))).

23. P.J. Landin, "The mechanical evaluation of
expressions", *Computer Journal* 6(1964), 308-320, develops a
"syntactically sugared", λ-less version of Church's notation, which
Landin later used to set out a formal specification of the semantics of
ALGOL 60. Others undertook to take the approach into the realm of
semigroups and categories.

24. In *Mathematical Reviews*
26(1963), #5766, Nerode wrote that McCarthy had introduced "yet another
definition of computability" via conditional expressions and recursive
induction. The former is "an arithmetical convenience for handling
definition by cases", and the latter, on which McCarthy laid great
stress, "is nothing else but the uniqueness of the object defined by a
recursive definition." "In the reviewer's opinion," he concluded, "the
problem of justifying the title is still open."

25. D.S. Scott, "Logic and programming
languages" (1976 Turing Award Lecture), in *ACM Turing Award
Lectures*, 47-62.

26. Dana S. Scott, "Outline of a mathematical
theory of computation", *Proceedings of the Fourth Annual Princeton
Conference on Information Sciences and Systems* (1970); revised and
expanded as Technical Monograph PRG-2, Oxford University Computing
Laboratory, 1970; 2.

27. *Ibid.*, 3.

28. *Ibid.*, 4-5.

29. Technical Monograph PRG-6, Oxford
University Computing Laboratory, 1971, p. 40; also published in *Proceedings
of the Symposium on Computers and Automata*, Microwave Research
Institute Symposia Series, Vol. 21, Polytechnic Institute of Brooklyn,
1971.

30. *What Can Be Automated? (COSERS)*,
ed. Bruce W. Arden (Cambridge, MA: MIT Press, 1980), 139. The committee
consisted of Richard M. Karp (Chair; Berkeley), Zohar Manna (Stanford),
Albert R. Meyer (MIT), John C. Reynolds (Syracuse), Robert W. Ritchie
(Washington), Jeffrey D. Ullman (Stanford), and Shmuel Winograd (IBM
Research).

31. C.A.R. Hoare, "The Mathematics of
Programming", in his *Essays in Computing Science* (Hemel
Hempstead: Prentice Hall International, 1989), 352.

32. "Towards a mathematical science of computation", 21.

33. "A basis for a mathematical theory of computation", 69.

34. For this reason, object-oriented programming, however appealing its notion of building complex structures from simple components, lacks any theoretical justification and runs against the grain of experience.