Computer architecture and theoretical computer science have different roots. Architecture grew out of projects begun in the 1940s to design high-speed electronic computing machines able to complete elaborate sequences of operations without human intervention. Its symbolic founding text is John von Neumann's 1945 "First Draft of a Report on the EDVAC,"a though early computer builders relied more directly on a series of lectures and reports disseminated the next year. Theoretical computer science grew from an academic desire to theorize about the fundamental characteristics and capabilities of automatic computing. The theoretical foundation of computer science was laid during the late-1950s and 1960s using intellectual materials scavenged from different fields. Alan Turing's 1936 paper, "On Computable Numbers, With an Application to the Entscheidungsproblem" provided the most prominent building block. In it, Turing introduced a definition of computability based on the operations of imaginary automata.
Popular imagination only has room for one "great man" per invention, and Turing's prominence in computer science has created a market for arguments that he must therefore have invented the computer itself. The fact that Turing and von Neumann knew each other has led to considerable speculation about the possible influence of Turing's paper on von Neumann's architectural approach. Yet no hard evidence has yet come to light showing that von Neumann had read or appreciated Turing's paper during the crucial period from early 1945 to mid-1946.
In this column, we present newly discovered archival evidence: the text of three lectures on "High Speed Computing" written by von Neumann in 1945.b This demonstrates von Neumann was well aware of Turing's work while he worked to define modern computer architecture. It also suggests von Neumann found Turing's work interesting as a model of computability but not as a source of ideas on computer architecture, a formalism with which to describe the design of a computer, or a way of justifying the construction of actual computers by pointing to their "universal" capabilities.
Between 1943 and 1945, a team working at the University of Pennsylvania's Moore School of Electrical Engineering designed and built ENIAC, the first programmable electronic computer. Before it was finished, they partnered with John von Neumann to propose and begin to design a successor. By April 1945, von Neumann had prepared a long document outlining a new approach in which programs were coded, along with the data they manipulated, as numbers in a large, addressable, and rewritable electronic memory. This "First Draft of a Report on the EDVAC" was widely distributed, as were the notes of a lecture series held at the Moore School in 1946 and reports issued by von Neumann's new team working at the Institute for Advanced Studies. These inspired the designers of the first generation of modern electronic computers, including those at the universities of Manchester and Cambridge, and Turing's own design for the ACE at the National Physical Laboratory. During the 1950s the term "stored-program computer" emerged to describe what had previously been called "EDVAC-like computers." This term mutated into an abstract "stored program concept" taken to characterize the essence of these machines, making it easy to assume that modern computers are the embodiment of a single novel idea.9
Some have suggested von Neumann took this single novel idea from Turing. The plausibility of this hinges on the philosophical question of what kind of innovation the modern computer was. Martin Davis asserted that Turing devised the "stored program concept" in his 1936 paper, implying that the invention of the computer was more than anything else an advance in mathematical thinking. This is clear in the title of his book: Engines of Logic: Mathematicians and the Origin of the Computer.6
Such claims have drawn attention to the relationship between Turing and von Neumann. Although the First Draft was (as its name suggests) not a finished publication it did include one citation, to a 1943 paper by Warren McCulloch and Walter Pitts on a connection between mathematical logic and neuron nets.13 That paper in turn cited Turing's 1936 paper and referred explicitly to his machine-based definition of computability, raising the question of whether von Neumann had read Turing's paper prior to his work on the First Draft. Andrew Hodges looked for direct evidence of this when researching his landmark biography of Turing.10 Von Neumann was indisputably aware of Turing, having written a reference in 1937 in support of the fellowship that allowed Turing to spend a year at Princeton University, in close proximity to von Neumann's own base at the Institute for Advanced Study. Hodges noted that the reference praised Turing's work in two areas of mathematics, but not with the 1936 paper. Hodges was able to contact one of von Neumann's Los Alamos collaborators, Stanislaw Ulam, who expressed a suspicion that von Neumann had read the paper by 1939 but could "not answer for sure."c
Jack Copeland has made the stronger assertion that von Neumann himself "repeatedly emphasized that the fundamental conception was Turing's." He had merely "placed Turing's concept into the hands of American engineers." Copeland quoted a short passage from a November 1946 letter von Neumann sent to Norbert Weiner, the founder of cybernetics, showing awareness of Turing's demonstration of a universal machine. He quoted at length passages from lectures delivered in 1948 and 1949 showing von Neumann's admiration for Turing's paper.d
We do not share Copeland's interpretation of these sources and see no solid evidence that von Neumann ever credited Turing with having inspired the design of EDVAC. Our own position was summed up in the title of an earlier Communications Historical Reflections column, "Actually, Turing Did Not Invent the Computer."8 The EDVAC design centered on what is often called the "von Neumann architecture" in which instructions were retrieved from memory, decoded, and executed using a single connection to main memory and a single arithmetic unit.9,15 We cannot point to any important features of this architecture that von Neumann might have derived only from Turing's paper.
Neither did the world need to read Turing to appreciate the potential of automatic computers. Before writing the First Draft von Neumann had visited groups at Harvard, Bell Labs, and the University of Pennsylvania that had initiated computer-building projects in complete ignorance of Turing's work. But such claims underline the importance of finding out what, if anything, von Neumann felt in 1945 about the relevance of Turing machines to computer-building projects.
Before proceeding to answer that question, we should acknowledge another controversy. Even those historians of early electronic computing who see the First Draft as a crucial and original document have disagreed about whether its key ideas should be credited to von Neumann or to the original ENIAC team. It is common to read claims that von Neumann was merely writing up ideas formulated by J. Presper Eckert and John Mauchly. Those who give full credit to the ENIAC design team often focus on the computer as a product of innovations in electrical engineering. Those, including Arthur Burks, another of the ENIAC team, who felt von Neumann made a crucial contribution, point to his abstraction from engineering details to produce the first coherent proposed architecture for EDVAC. Surviving evidence is inconclusive, but in our book ENIAC in Action we did our best to plausibly divide credit for different aspects of the EDVAC design.9
After the completion of ENIAC in Action, one of us (Priestley) returned to the archive of Herman Goldstine's papers at the American Philosophical Society in Philadelphia. Goldstine had been von Neumann's closest collaborator within the ENIAC group, and chose to have the First Draft typed up and widely distributed.
Hiding in Goldstine's papers was the typescript of a series of three short lectures by von Neumann on "High Speed Computing." They provide a more complete and explicit discussion of the connection of Turing's 1936 paper to the design of actual computers than the documents historians have previously relied upon. We believe they predate any prior documented reference by von Neumann to Turing's 1936 paper. Through not dated, from internal evidence and comparison with other documents from the period, we conclude the text dates from mid-to-late 1945; we justify that assertion below.
As shown in Figure 1, Lecture 3 began with the words "The problem of developing a computing machine can be considered as a problem in logic," which in this context referred to "logical control" or the automatic sequencing of operations. Von Neumann's approach to computer architecture was deeply shaped by his background in logic. His plan for EDVAC was a simpler, cleaner, and more practical design than any of the earlier attempts to build a general-purpose automatic computer.
The text shows that von Neumann knew Turing's 1936 paper and fully appreciated the significance of the universal machine described in it. He first described Turing's machine concept and its connection to the question of effective calculability: "We shall consider two systems of logic which could be used in building a computing machine. The first, developed by Turing, is essentially a logic machine. Turing considered setting up a mathematical apparatus for the decidability of mathematical problems. More specifically he was interested in determining when an arithmetic function can be constructed. Instead of treating problems in the usual fashion of starting with a set of assumptions and then proving theorems, Turing set up a hypothetical machine to construct the function.
"The Turing machine consists of two parts; one is permanent, and the otherthe recording mediumcan be changed ... It is composed of a long paper band with symbols recorded and an apparatus to sense these symbols, put on new ones, and erase old ones. There are a finite number of states of the machine. Let the range of the indication i of those states be i = 1,2, N. Let the state of a square of tape be j, where j = 1, 2, M. At every moment the machine inspects the tape and then does something. That is, from every state (of machine and tape) (i,j), they move to another (i', j') and the tape is moved right or left by one unit. If we think of this in terms of graphs we have an arrow from one point to another and a sign."
This description is easier to follow than Turing's own, and von Neumann's description of state transitions in terms of a graph anticipates the later development of state transition networks as a visual model for finite state automata.
Von Neumann was clear on the limited usefulness of this model of computation, which had been designed to prove a theoretical point about mathematics, as a guide to the capabilities of actual automatic computers. "Suppose this machine is provided with a tape with a finite number of symbols, the question is whether there is a permanent apparatus which will solve the problem by the Turing method. There is a finite number of different steps that the machine can do. However, the machine can do steps an infinite number of times. Hence, a problem whose solution can be broken down into a finite or infinite number of parts, but involving only a finite number of different steps, can be done on this machine. Here the analogy to a high-speed computing machine breaks down, for one cannot wait for the machine to go all eternity for his answer."
Computer builders, von Neumann realized, must be concerned more with practical than theoretical limits to computability.
Before moving on to the next topic, von Neumann then described Turing's universal machine concept: "A Turing machine is defined as 'adequate' for a particular problem if it can be solved by means of a suitable tape and apparatus. A 'universal' machine is one which can construct any arithmetic function that can be done by a particular Turing machine. Common sense might say that a universal machine is impossible, but Turing proves that it is possible. The idea of a universal machine is simple and neat. To build this machine one decides on a code to describe each particular Turing machine. Then one puts the definition of each Turing machine to a tape. The new machine reads the definition of a Turing machine and then imitates it."
Computer builders, von Neumann realized, must be concerned more with practical than theoretical limits to computability.
He proceeded to make the first contribution to what later became a popular game of identifying the smallest number of states and symbols a Universal Turing Machine could operate with.
Later popularizers have focused on the universal machine as the heart of Turing's paper, to the extent that many people believe that a "Turing Machine" is necessarily a universal machine. It takes a conscious effort to notice how unusual this focus was in 1945. Turing's paper had been little cited, and the attention it did receive, most famously a short review by Alonzo Church that introduced the phrase "Turing Machine," treated it as a contribution to work on decidability and ignored the universal machine part of the paper.4 In that context the universal machine was almost a diversion, developed in more detail than necessary to prove Turing's mathematical argument. We are not aware of any earlier recapitulation of the universal machine concept by any author.e Even Martin Davis, who in 1958 was one of the first to note the potential of the universal machine as a model for what could be calculated by real computers, nevertheless advised readers that the page he devoted to the topic was "a digression and may be omitted without disturbing continuity."5
Von Neumann then moved to the lecture's main topic, "The Logic of Pitts," spending more than twice as much space on neuron networks as he had on Turing machines. This reflects von Neumann's deep involvement in the establishment of what would soon be called cybernetics. In January 1945, von Neumann, Howard Aiken, and Nobert Wiener convened a meeting of people "interested in communication engineering, the engineering of computing machines, the engineering of control devices, the mathematics of time series in statistics, and the communication and control aspects of the nervous system." Wiener himself had been working during the war with electronics, trying to produce an automatic control unit for anti-aircraft guns able to predict the trajectory of enemy pilots.7
Historians remember the January 1945 event as one of several that laid the groundwork for the emergence of cybernetics a few years later.12 The meeting had a strong focus on computation and applied mathematics: as well as McCulloch and Pitts and other leading brain researchers, invitees included mathematicians and statisticians with links to practical and automated computing, such as Herman Goldstine and Leland Cunningham of the Ballistics Research Lab. Immediately afterward, participants were filled with excitement for follow up plans for collaborative research, including the establishment of a Teleological Society. Working groups were formed to explore the application of automatic computers to statistical problems and to differential equationsf But when plans for a second teleological meeting faded, work shifted to the well-known series of "Macy Conferences" organized by McCulloch and others from 1946 onward. Von Neumann remained involved, but the series settled down with a mix of participants featuring fewer applied mathematicians and more high-profile participants from disciplines such as sociology, psychology, psychiatry, and anthropology.10 In 1948, Weiner published Cybernetics: Or Control and Communication in the Animal and the Machine which pushed the new way of thinking onto the pages of newspapers and magazines. The interchangeability of organisms and mechanisms remained one of the central ideas of cybernetics.
Weiner had introduced von Neumann to the 1943 McCulloch and Pitts paper we mentioned earlier in this column. Work by Claude Shannon had already established an equivalence between digital circuits and expressions in propositional logic. McCulloch and Pitts went further, asserting that their "nets" of abstract neurons, coupled with "tapes" and suitable "scanners," had equivalent computational capabilities to Turing machines and other computational agents: "If any number can be computed by an organism, it is computable by these definitions, and conversely." Initial interest in "nervous nets" was thus quite different from the later shift to neural nets in artificial intelligence, which was motivated by a desire to avoid symbol processing and propositional logic rather than to implement them.
To the cyberneticians, digital control circuits, brains, and logical propositions were different ways of expressing the same relationships between inputs and outputs. The excitement of this idea runs through the First Draft, and is reflected in von Neumann's use of biological language (EDVAC's major components were called "organs" and its storage "memory") and deployment of an abstract neuron-inspired notation to represent computing circuits (see Figure 2).
In the lecture von Neumann used the same notation to illustrate the applicability of "the logic of Pitts" to computer design. His examples showed simple configurations, including a chain of neurons for memory ("we would like to design a circuit which would learn and unlearn"), a binary adder, and a counter. The lecture stops abruptly, without getting to the issue of automatic ("logical") control which von Neumann had earlier suggested was the major unsolved challenge. More space is given over to the neuron notation than to anything else, and relatively little to electronic storage and its organization (a major topic in the First Draft).
The lecture contains several implicit references to ENIAC and EDVAC, evidence that von Neumann was writing for a broad audience at a time when ENIAC remained secret, that is, before its February 1946 press launch. As in the First Draft, he preserved a deliberate vagueness, presenting as theoretical possibilities things the ENIAC team had already proven experimentally. For example, he stated that a "fast" machine able to multiply two ten-digit numbers in 0.001 second was not yet a reality but was achievable with "existing objects of computing." Ten decimal digits was the size of ENIAC's standard numbers, placing an upper bound for the lecture date at some point before the full ENIAC's first successful use in December 1945.
Noting the simplicity and generality of the examples in the lecture as opposed to the more complex networks presented in the First Draft, we originally suspected that the lectures contained von Neumann's first experiments in using the neuron notation. A plausible venue for their delivery would then have been the January 1945 meeting of the nascent Teleological Society on the first day of which, according to Wiener, "von Neumann spoke on computing machines."g That would make the adder circuit in the lecture, which differs significantly from the First Draft version, an early, discarded design.
However, we then re-examined a letter in which Herman Goldstine sent von Neumann comments on the text of the First Draft, including a sketch of the design of "an adder that Pres [Eckert] and John M[auchly] are patenting."h Von Neumann's adding circuit in the lectures (see Figure 3), closely resembles this sketch. Goldstine also suggested some changes to the notation, such as adding arrowheads to the lines linking the neuron symbols. These appear in the lecture but not in the First Draft, the text of which was not altered before is was circulated in Junei These facts suggest that the lecture was written after von Neumann received Goldstine's letter in mid-May 1945 and used simple diagrams for pedagogical reasons only.
Thus we are confident the notes date from the summer or fall of 1945. This was a crucial period in von Neumann's work on computing, during which he continued to revise his EDVAC code and worked on a complex sort routine designed to test out the potential of the new approach to automatic computing.15 By the end of the year his attention had shifted to the IAS computer project, which settled on a revised and highly influential version of the EDVAC design. Combined with his multiple consultancies and contributions to IBM's early efforts in electronic computing, this reminds us that von Neumann's contributions to early electronic computing go far beyond simply writing the First Draft, and were made possible by his movement between different groups and communities.1
We then combed through what we could reconstruct of von Neumann's calendar to identify a possible venue for the lectures. He gave a talk with a similar title, on "High-speed computing devices and mathematical analysis," at the Canadian Mathematical Congress in June 1945, but Garrett Birkhoff recalled that the focus of that talk was on numerical methods and simulation in fluid dynamics.3
The closest match to the lecture we found was in a memoir from mathematician Calvin Mooers, who was part of a computer building project at the Naval Ordnance Lab headed by John Atanasoff. Von Neumann was an initiator of and consultant to that project. Mooers recalled that "very early" in the project, which he joined in August 1945, the team met with von Neumann who "cordially received us, and then jumped into an advanced (for us) logical discussion about the design of a computer using, as I recall the Pitts and McCulloch symbolism for neural connections." They were not "intellectually ready" for this, because the "language and concepts were not from electronics and circuits, which we might better have assimilated..."14
Mooers' diary and notebooks document several meetings with von Neumann, the earliest on August 29 when Mooers learned about ENIAC and plans for EDVAC.j On October 28, Mooers and other members of the NOL team traveled to Philadelphia to visit ENIAC, and then moved on to a meeting at the IAS where "von Neumann reviewed some work of Turing and Pitts" before he "lectured on his tentative coding scheme for the computer." Mooers' notebook includes the citation for Turing's paper, with the comment "This is on a math computing machine to decide certain problems in math"; see Figure 4. On his return to Washington, Mooers requested a photostat copy of Turing's paper from the library but, unlike the First Draft, he never recorded reading it.k
Figure 4. Calvin Mooers' notebook records topics covered during his meeting with von Neumann on October 28, 1945: Turing's 1936 paper, Pitts' mathematical representation of neurons, and von Neumann's work on instruction set design.
Mooers' experience of von Neumann spontaneously launching into similar material in October builds our confidence in a mid-1945 date for preparation of the lecture text. Von Neumann gave many lectures and assisted many computing groups, undoubtedly recycling material between then. He obviously hadn't prepared the text specifically for this occasion, not least because it is coy about the details of projects he had already discussed with Mooers. The material von Neumann followed it with on that occasion, describing his new approach to logical control, would have been the obvious content for a "lecture 4" to solve the problem posed at the start of lecture 3.
Mooers did not reference Turing in his efforts to design a computer and instruction set. In March 1946, however, he did track down the work of McCulloch and Pitts and used the neuron notation and cybernetic terminology to sketch out plans for a "thinking machine." He discussed it with Pitts that summer, noting in his diary that he told him "how by use of a magnetic edvac type machine a device could be made which would trace through a nervous net. Showed him how a 'Turing Machine' (which it is) can be elaborated to do the job."l Not long after Mooers' boss, John V. Atanasoff, ordered him to work on more useful matters.
Even before learning of the lecture notes on "High Speed Computing" we believed that von Neumann was almost certainly familiar with Turing's 1936 paper prior to beginning work on the First Draft. His later remarks showed that he fully understood its use as an abstract model of computation, and there was no reason to believe he suddenly developed this understanding after 1945. The new evidence confirms that von Neumann had read and fully understood Turing's paper around the time he was creating and refining his abstract design of EDVAC.
More interestingly, the lecture gives us a sense of the contexts in which von Neumann did, and did not, find Turning machines relevant. They appear in a tutorial role, introducing an abstract model of computation to make a point about the equivalence of different possible computers with respect to the computations they could perform "given all eternity." That resembles the use of the concept by modern computer science popularizers, though its coupling with discussion of neurons and the creation of machines able to learn reminds us that for von Neumann, as for other founders of cybernetics, enthusiasm for theories of computation was bound up with much grander visions. The example of Mooers suggests that von Neumann successfully communicated this cluster of ideas to at least one recipient.
While Turing machines do not appear in von Neumann's work on computer architecture and logical control, they are prominent in his later work toward a "general and logical theory of automata."2 His lecture at the 1948 Hixon symposium showed, in the words of historian William Aspray, that he "had in mind the McCulloch-Pitts and Turing contributions as the foundation for his new theory." Von Neumann developed these ideas further over the next few years, culminating in a major work on cellular automata and a series of lectures on the computer and the brain, both of which remained unfinished at the time of his death.
Von Neumann freely acknowledged the contribution of Turing's 1936 paper to his work on automata theory but made no such connections in his discussion of computer design. Now that we know how clearly and concisely von Neumann could explain the universal Turing machine in 1945, its absence in his other reports, lectures, and letters of the 19451946 period speaks loudly, like the dog that Sherlock Holmes realized had failed to bark during the night. Von Neumann deployed it in an introductory lecture, but not for other purposes. He made no reference to any feature of the Turing machine in the First Draft or his other 19451946 detailed writings on computer architecture and instruction sets. Neither did he mention Turing's demonstration of universality (or related work by Post and Church) in his other speeches and letters lobbying for the construction of EDVAC-like computers.m In contrast the neuron notation and cybernetic language did make it into the First Draft, though as a convenient way to describe digital logic rather than as a source of architectural inspiration. The abstraction from constraints of space and time that eventually made Turing machines so useful for computer scientists looking to lay theoretical foundations for their new field made them irrelevant to people trying to design the first real electronic computers.
3. Birkhoff, G. Computer Developments 193555, as Seen from Cambridge, USA. In A History of Computing in the Twentieth Century, N. Metropolis, J. Howlett and G.-C. Rota, Ed., Academic Press, New York, 1980, 2130.
a. See http://bit.ly/2LbZtcI
b. J. von Neumann, "High Speed Computing," n.d. circa 1945, in the Herman Heine Goldstine Papers, American Philosophical Society, Philadelphia, PA (hereafter HHG-APS), box 49, folder "JvN undated #5".
d. Copeland has made similar points in several venues, but for accessibility we are working here from his online publication "Turing, Father of the Modern Computer" with Dianne Proudfoot, http://www.rutherfordjournal.org/article040101.html#chapter06.
e. We are deeply grateful to Andrew Hodges for his advice on this point. The spread of Turing's ideas in the 1950s is discussed by Lisebeth De Mol in https://plato.stanford.edu/entries/turing-machine/.
g. Wiener, letter to Rosenblueth, 1945 Jan 24, quoted in S. J. Heims, John von Neumann and Norbert Weiner: From Mathematics to the Technologies of Life and Death. MIT Press, Cambridge, MA, 1980, 185186.
m. For example, a lengthy 27 August 1945 report to the Navy Ordnance Department on "Computer Services" (HHG-APS, box 9). See Priestley14 (2018, 92-3) for a discussion of the term JvN used instead, namely "all-purpose," and its difference from Turing's notion of "universal."
The Digital Library is published by the Association for Computing Machinery. Copyright © 2020 ACM, Inc.
No entries found