Out of Their Minds

In short

A pleasant gallery of some famous computers scientists. The choice is of course disputable, e.g. concerning artificial intelligence. The glossary is a bit weak. An easy-reader in any case.

Table of Contents

• Introduction
• Part 1: Linguists

  • John Backus

    
    From von Neumann's scale factors to floating point numbers (Speedcoding). Fortran. Algol (local variables, support for recursion). Backus-Naur form (BNF). FP (a functional language).

  • John McCarthy

    
    The author of LISP. Recursion and eval. Frame problem, nonmonotonic reasoning, circumscription. Propositional calculus (Boole), predicate calculus (Frege).

  • Alan Kay

    
    Smalltalk
• Part 2: Algorithmists

  • Edsger Dijkstra

    
    Shortest path (ever growing "core set"). Critical section, mutual exclusion, semaphores. Dining philosophers (Hoare).

  • Michael Rabin

    
    Turing's computability, Hilbert's Enscheidungsproblem (decision), Gödel and Epimenides, Turing's halting problem. Dana Scott. Finite state machines (Chomsky and context-free grammars). Nondeterministic choices. One-way functions (von Neuman's "middle squaring"). Inherent computational difficulty. Randomized primality test (based on "witnesses", with Vaughan Pratt). Power of randomness.

  • Donald Knuth

    
    The Art of Computer Programming. LR(k) parsing, lookahead. Attribute grammars. Reduction. Pattern matching. TEX and METAFONT.

  • Robert Tarjan

    
    Depth-first search. Planarity testing of graphs. Union-find and amortization. Self-adjusting data structures: "splay-trees". Persistent data structures for temporal databases.

  • Leslie Lamport

    
    The Bakery Algorithm for mutual exclusion. Distributed clocks. Fault tolerance with digital signatures. Hierarchical structured proofs. LATEX.

  • Steve Cook and Leonid Levin

    
    Kolmogorov's perebor problems. Satisfiability in predicate and propositional calculus. Exponential vs polynomial time. NP-complete problems. Reducibility.
• Part 3: Architects

  • Fred Brooks

    
    Iverson's APL. Maskable interrupts. System/360. Intelligence amplification vs artificial intelligence.

  • Burton Smith

    
    Dataflow architecture: parallelism in space. Memory latency, HEP: many tasks on each processor. Hot potato routing.

  • Danny Hillis

    
    Emergence. Connection Machine. Leiserson's fat trees.
• Part 4: Sculptors of Machine Intelligence

  • Edward Feigenbaum

    
    Heuristics: problem-solving techniques. EPAM: Elementary Perceiver and Memorizer. Deduction vs induction (Peirce). Expert systems: Mycin, Dendral.

  • Doug Lenat

    
    Constraint logic programming languages. Popper's falsiable hypotheses. AM (Automated Mathematician), thrashing. Minsky's frames. Microtheories, global vs local consistency. Cyc: multiple inference engines.

Some quotes

p 5, John Backus:

We didn't know what we wanted and how to do it. It just sort of grew.

p 19-20 Comparing:

    c := 0
    for i := 1 step 1 until n do
        c := c + a[i] * b[i]

    Def Innerproduct = (Insert +)(ApplyToAll *)(Transpose)

• no hidden state
• no parameter passing
• no repeated calculation

p 49, Alan Kay:

[B]usinessmen are more like engineers than like scientists. They basically want to do more than understand. At some point with new phenomena, you have to spend some time understanding it, not just worrying about what are we going to do with it.

p 68, Michael Rabin

We should give up the attempts to derive results and answers with complete certainty.

p 146

The guessing part is nondeterministic and the checking part is polynomial.

p 168, Fred Brooks

The waterfall model of specify, build, test is just plain wrong for software.
[T]he principal intellectual problems in software engineering are problems of scale, not how to write little programs but how to manage the complexity of big things.

p 202, Daniel Hillis

Evolution doesn't solve a problem. Evolution invents a problem and solves it at the same time.

p 228

To Popper, a theory is scientific if it is falsiable, that is, if an experiment could show the theory to be false.
Experimental falsiability doesn't work for mathematics.

p 239, Doug Lenat

If you have the knowledge, it's a trivial problem. If you don't have the knowledge, it's an impossible problem.