Notes from:
[Bhatta2021] Bhattacharya, Ananyo. The Man from the Future: The visionary life of John von Neumann
Book: Mathematical Foundations of Quantum Mechanics, by JvN (p. 41-46)
JvN re: quantum mechanics (p. 60):
that events appear to be linked to each other in the familiar everyday world is irrelevant … because what we see is the average of countless quantum interactions
Operators in Hilbert space (p. 61)
Goedel 2nd incompleteness theorem (p. 117):
- no system complex enough to contain arithmetic can be proven to be consistent using the tools of the system itself
- it is impossible to prove that contradictory statements such as 2+2=5 can never be proved
Article: First draft of a report on the EDVAC (p. 122)
“Monte Carlo” methods (p. 133-134)
Programming with flowcharts (p. 135)
“method of middle squares” for pseudo-random numbers (p. 138) (See also article The middle of the square by Brian Hayes)
The complete computer program for the 2nd Monte Carlo run ever, by Klari von Neumann (p. 137):
- Can be run today on an ENIAC emulator (p. 138)
- For the code, see the book ENIAC in action, Haigh et al
Minimax theorem (p. 143)
Minimax theorem first appears in the article On the theory of parlor games (p. 143):
- “draws” depend on chance
- “steps” are player actions based on human choices
- “minimax” means a strategy to minimize the maximum loss
Paper concludes with a proof that every 2-player zero-sum game has a solution that is either (p. 147):
- a “pure” strategy, e.g., pick heads consistently
- a “mixed” strategy, e.g. pick heads / tails at random
Book: Theory of Games and economic behavior, by John von Neumann (p. 151)
Numeric “utility” or “happiness” values need to be assigned to make game theory work (p. 160)
How to calculate “utils” (p. 161):
- Imagine a birthday party
- Instead of the party, you can have a lotto ticket
- If it wins, you go to “heaven” (100 utils)
- If it loses, you go to “hell” (0 utils)
- If the ticket would need to give you a 75% chance of winning for you to trade your party for it, the party is worth 75 utils
ways to represent games (p. 162):
- Extensive form: a game tree; can grow quite large; each branch is a possible move, each leaf is a final outcome of the game
- Normal form: shows moves and payoffs as a 2-d grid or table
When all moves are visible to both players, it’s a game of “perfect information”, all of which have a “solution”
NB. there are at least 10^120 games of chess, according to Claude Shannon
“Chess is not a game” – von Neumann
JvN shows why the key to poker is “bluffing”, aka betting big with bad hands (p. 166)
How often players should bid high with a weak hand depends on the ratio of high to low stakes
If you only bid high with good hands, opponents learn to fold, reducing your winnings
The book Theory of Games and Economic Behavior explains why monopolies occur: In a 3-person game, a rational player forms a coalition to make the game 2 vs. 1
- 2 buyers, 1 seller: buyers form a coalition to drive down seller’s price
- 2 sellers, 1 buyer (aka “monopsony”): sellers collude to drive up the price
Game theorists designed an FCC auction (p. 177):
- “simultaneous, ascending auction”
- “the greatest auction ever” (NYT – link)
Kahnemann & Tversky, “prospect theory” (p. 178)
Most useful application of game theory: auction design
Price Equation (p. 180)
“Tit for tat” is optimal strategy for repeated prisoners’ dilemma (p. 181)
- proved by Anotol Rapoport
- cooperate by default
- be selfish if the other guy is selfish
RAND is a non-profit (p. 187)
AMP: Applied Mathematics Panel; did “operations research”
Game theory “utility” -> “military worth” (p. 188)
The Compleat Strategyst, satirical book from RAND
Von Neumann’s student ran RAND; he consulted for them (p. 190)
Dantzig (of Linear Programming fame) and von Neumann met; von Neumann sees connections between LP and the minimax theorem (p. 191)
Shapley values of a cooperative game (p. 196)
Gale-Shapley “deferred acceptance” algorithm to solve the stable marriage problem (p. 197)
Paper: John Nash, The Bargaining Problem, re: 2-person cooperative games, and how to divide the “surplus” created when a deal is struck
Nash equilibria (p. 201):
- players can not communicate or team up
- there are certain outcomes for all games in which no player can do any better than unilaterally changing their strategy
- works for any number of people / players
- doesn’t have to be zero-sum
Paper: Some Experimental Games, by Merrill Flood (at RAND)
Prisoners’ Dilemma (p. 205):
- interestingly, the only Nash equilibrium is for the prisoners to rat on each other (a.k.a. both defect)
- good discussion p. 205-208 of how many people cooperate even if it’s more rational not to (using RAND researchers as guinea pigs)
Eisenhower contemplated nuking China in the 1950s (p. 209)
Paper: Selection and Use of Strategic Bases, by Wohlstetter (p. 214):
- Used game theory to determine why we should not station our bombers in Europe
First ICBMs: 1957-58 (p. 218)
Paper: Defense in Atomic War, by John von Neumann (p. 221)
U.S. military guidelines for small-scale nuclear warfare: JP-372 on Joint Nuclear Operations (p. 223)
Alex Ellery at Carleton University: RepRap (3-d printer) but for the outer space environment (p. 226)
Book: Theory of self-reproducing automata by John von Neumann (p. 226)
McCulloch & Pitts: early neural networks (p. 226)
Article: Man viewed as a machine, by John Kemeny (p. 232)
John von Neumann developed cellular automata (p. 234):
- endless 2-d grid
- 29 states
- cell can only talk to 4 contiguous neighbors
- reproduces a universal Turing machine
- self-replicating! (p. 235)
- first simulation ran in 1994 (p. 236)
Conway Game of Life description:
- Found a much simpler representation that could still provide Turing completeness and self-replication
Tommaso Toffoli Ph.D thesis:
- reversible automata exist
- any automaton can be made reversible by adding another dimension (p. 244)
- designed CAM: Cellular Automata Machine
Wolfram and cellular automata (p. 245):
- Matthew Cook proof: Rule 110 is Turing complete
- Book: A new kind of science (p. 251)
Nils Aal Baricelli:
- Artificial life (p. 254)
- symbiogenesis: cooperation, not just competition
- one-dimensional automata that presage Wolfram’s automata
- Evolved mechanisms to play tic-tac-toe, chess
First conference on artificial life, Los Alamos 1987 (p. 257)
Langton Loops (p. 258)
Lab-made organism by Craig Venter (p. 261)
von Neumann probes – send automata to terraform planets (p. 263)
Book: Kinematic self-replicating machines, by Freitas and Merkle; catalogs self-replicating technologies (p. 264)
Richard Laing:
- proved that an automaton need not start with a complete description of itself in order to replicate
- NASA “SRS” group (Self Replication Systems)
Book: Engines of Creation, by Eric Drexler – on nanotechnology
Article: There’s plenty of room at the bottom, by Richard Feynman
Thomas Schelling (p. 270):
- Economist
- Investigated segregation in cities
- segregation can result from even mild proclivity towards neighbors with same ethnicities
John McCarthy attended the John von Neumann lectures on automata
Book: The Computer and the Brain, by John von Neumann – his last book, prepared while dying
Perceptron: improvements by Frank Rosenblatt on the earlier McCulloch-Pitts neuron; similar to today’s neural networks
John von Neumann invented the term “technological singularity” in discussion with Ulam (p. 276)
Mandelbrot says John von Neumann was shunned by various groups in Princeton (p. 277-278)
Goedel wrote to John von Neumann re: P vs. NP problem just before the latter’s death; this was years before P vs. NP was first rigorously stated in 1971
John von Neumann deathbed conversion to Catholicism (p. 279); he was thinking of Pascal’s Wager
Article: Can we survive technology?, by John von Neumann