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.(16)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.
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 main mathematical novelty 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 the metamathematical project of providing the "correct" approach to semantics.One 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 element l of the set L of locations to its value σ(l) in V, the set of allowable values. A command effects a change of state; it is a function γ from the set of states S into S. Storing a command means that can take the form γ(σ), and hence σ(l)(σ) should be well defined. Yet, "[t]his is just an insignificant step away from the self-application problem p(p) for 'unrestricted' procedures p, and it is just as hard to justify mathematically."(28)
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.(32)He extended the analogy at the conclusion of his 1963 article by reference to later successes in mathematical physics:
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.(33)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.
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.