John von Neumann – Game Theory and the Digital Computer

John von Neumann (1903-1957)

On December 28, 1903, Hungarian and American pure and applied mathematician, physicist, inventor and polymath John von Neumann was born. He made major contributions to a number of fields including mathematics, physics, economics, computing, and statistics. He was a key figure in the development of game theory, the concepts of cellular automata, and the digital computer. He is definitely one of the candidates to write several biographical articles of, each with a different aspect of his work. For me as a computer scientist, of course the so-called von-Neumann architecture principle on which today’s computers are based is of importance. Thus, in this article I will consider his contributions to computer science besides the biographical data.

“I think that it is a relatively good approximation to truth — which is much too complicated to allow anything but approximations — that mathematical ideas originate in empirics.”
– John von Neumann, [4]

John von Neumann – Early Years

Von Neumann was born Neumann János Lajos in Budapest, Austro-Hungarian Empire, to wealthy Jewish parents as the eldest of three brothers. His father, Neumann Miksa (Max Neumann) was a banker, who held a doctorate in law, and in 1913 was elevated to nobility acquiring the hereditary title margittai. Neumann János became margittai Neumann János (John Neumann of Margitta), which he later changed to the German Johann von Neumann. He was an extraordinary child prodigy in the areas of language, memorization, and mathematics. As a 6-year-old, he could divide two 8-digit numbers in his head and by the age of 8, he was already familiar with differential and integral calculus. By the age of 19, von Neumann had published two major mathematical papers and he received his Ph.D. in mathematics at University in Budapest at the age of 22.

From Berlin to Princeton

Starting in 1926, he taught as a Privatdozent at the University of Berlin, the youngest in its history and by the end of 1929, he had published thirty-two significant papers, at a rate of nearly one major paper per month. Von Neumann’s alleged powers of speedy, massive memorization and recall allowed him to recite volumes of information, and even entire directories, with ease. In 1930, von Neumann was invited to Princeton University, New Jersey, where he was offered a faculty position in 1933 at the Institute for Advanced Study, a position which he should keep until his death.

Manhattan Project and Hydrogen Bomb

“A large part of mathematics which becomes useful developed with absolutely no desire to be useful, and in a situation where nobody could possibly know in what area it would become useful; and there were no general indications that it ever would be so.”
– John von Neumann, [11]

Besides his major contributions to set theory, geometry, measure theory, ergodic theory, operator theory, lattice theory, quantum mechanics and quantum logics, game theory, mathematical economics, linear programming, mathematical statistics, and nuclear weapons, we want especially to focus on his contributions in computing here. Actually, von Neumann was a founding figure in computing. During his work in Los Alamos during the development of the hydrogen bomb, von Neumann and Stanislaw Ulam developed simulations on von Neumann’s digital computers for the hydrodynamic computations.[5] During this time he contributed to the development of the Monte Carlo method, which allowed solutions to complicated problems to be approximated using random numbers. Because using lists of “truly” random numbers was extremely slow, von Neumann developed a form of making pseudorandom numbers.

The Principles of Game Theory

John von Neumann made outstanding contributions in many areas of mathematics. As early as 1928, an essay by the mathematician Émile Borel on minimax properties had led him to ideas that later resulted in one of his most original designs, game theory. In 1928 von Neumann proved the min-max theorem for the existence of an optimal strategy in “zero-sum games”. In 1944, together with the economist Oskar Morgenstern,[16] he wrote the classic book The Theory of Games and Economic Behavior, which also deals with the generalization to n-player games, which is important for economics. He thus became the founder of game theory, which he applies less to classic games than to everyday conflict and decision-making situations in which the intentions of the opponent are not fully understood (as in poker).

The Computer and the von Neumann Architecture

While consulting for the Moore School of Electrical Engineering at the University of Pennsylvania on the EDVAC project, von Neumann described a computer architecture in which the data and the program are both stored in the computer’s memory in the same address space, a principle which still holds for today’s computers unlike the earliest computers that were ‘programmed’ by altering the electronic circuitry. Although the single-memory, stored program architecture is commonly called von Neumann architecture (sometimes also referred to as Princeton Architecture) as a result of von Neumann’s paper [8], the architecture’s description was based on the work of J. Presper Eckert and John William Mauchly,[6] inventors of the ENIAC [7]. John von Neumann also consulted for the ENIAC project. He recognized the need for parallelism in computers but equally well recognized the problems of construction and hence settled for a sequential system of implementation.[3]

Von Neumann Architecture

Von Neumann’s report was intended as a discussion report with the ENIAC group and initially remained unpublished, but quickly circulated in scientific circles. Virtually all modern computers are based on von Neumann’s idea. Many ideas of von Neumann’s architecture had already been worked out by Konrad Zuse in 1936,[9] documented in two patent specifications in 1937, and for the most part mechanically realized in the Z1 machine as early as 1938. In 1941, Konrad Zuse, together with Helmut Schreyer, built the Zuse Z3, the world’s first functional digital computer. However, it is considered unlikely that von Neumann was aware of Zuse’s work when he presented his architecture in 1945.

Reproducible Machines

He then lobbied to build an improved computer at the Institute for Advanced Study. The IAS machine, which began operating in 1951, used binary arithmetic — the ENIAC had used decimal numbers — and shared the same memory for code and data, a design that greatly facilitated the “conditional loops” at the heart of all subsequent coding.[2] Stochastic computing was first introduced in a pioneering paper by von Neumann in 1953. However, the theory could not be implemented until advances in computing of the 1960s. In his later years, von Neumann puzzled over the question of whether a machine could reproduce itself. He created the field of cellular automata without the aid of computers, constructing the first self-replicating automata with pencil and graph paper. Conceptually, this work anticipated later discoveries in genetics. Beginning in 1949, Von Neumann’s design for a self-reproducing computer program is considered the world’s first computer virus, and he is considered to be the theoretical father of computer virology. Von Neumann’s cellular automata form an important basis for the research discipline of artificial life and enable the simulation of biological organisation, self-reproduction and evolution of complexity. Donald Knuth cites von Neumann as the inventor, in 1945, of the merge sort algorithm, in which the first and second halves of an array are each sorted recursively and then merged.

Cybernetics

“Young man, in mathematics you don’t understand things. You just get used to them.”
– John von Neumann

Together with Norbert Wiener, von Neumann organized an interdisciplinary meeting with engineers, neuroscientists and mathematicians in Princeton towards the end of winter 1943/44 on commonalities between the brain and computers and thus the foundations of cybernetics, which Wiener first described in detail in 1948. Von Neumann finally led his own computer project, the IAS computer, at the Institute for Advanced Study from 1949, where he was able to realise his ideas, including many programming concepts. He was responsible for subprograms with parameter transfer via a reference to a memory location, various methods of generating random numbers (including the mid-square method and the reject method) and the merge sort. He contributed significantly to the use of binary codes in computer systems and propagated the use of flowcharts, in which he also provided a kind of assertions that can be regarded as precursors for loop invariants in the Hoare calculus.

Honours

Von Neumann received two Presidential Awards, the Medal for Merit in 1947 and the Medal for Freedom in 1956. Also in 1956 he received the Albert Einstein Commemorative Award and the Enrico Fermi Award. A lifelong agnostic, shortly before his death he converted to Roman Catholicism. Von Neumann died a year and a half after the diagnosis of cancer in 1957.

Raymond Flood, Turing and von Neumann, [17]

References and Further Reading:

• [1] O’Connor, John J.; Robertson, Edmund F., “John von Neumann“, MacTutor History of Mathematics archive, University of St Andrews.
• [2] John von Neumann at Encyclopedia Britannica
• [3] John Louis von Neumann at the National Science Foundation
• [4] John von Neumann, “The Mathematician“, in The Works of the Mind (1947) edited by R. B. Heywood, University of Chicago Press, Chicago
• [5] Please Don’t Ignite the Earth’s Atmosphere…, SciHi Blog
• [6] John William Mauchly and the Electronic Computer, SciHi Blog
• [7] ENIAC – The First Computer Introduced Into Public, SciHI Blog
• [8] John von Neumann: First Draft of a Report on the EDVAC. In: IEEE Annals of the History of Computing. Vol. 15, Issue 4, 1993, doi:10.1109/85.238389, S. 27–75 (PDF, 9,556 MB)
• [9] Konrad Zuse – The German Inventor of the Computer, SciHi Blog
• [10] Norbert Wiener and the Science of Cybernetics, SciHi Blog
• [11] John von Neumann, “The Role of Mathematics in the Sciences and in Society” (1954) an address to Princeton alumni, published in John von Neumann : Collected Works (1963) edited by A. H. Taub ;
• [12] John von Neumann at Wikidata
• [13] Timeline for John von Neumann, via Wikidata
• [14] John von Neumann at zbMATH
• [15] John von Neumann at Mathematics Genealogy Project
• [16] Oskar Morgenstern and the Game Theory, SciHi blog
• [17] Raymond Flood, Turing and von Neumann, Gresham College @ youtube