W. Daniel Hillis

Detailed Review:

Preface: Magic in the Stone
Just generally hyperbolic.

Chapter 1: Nuts and Bolts
Incomprehensible tic-tac-toe motivating example, but the cute pictures of mechanical logic gates rather redeem it. One of the main points is that it's not the transistor technology that makes a computer, its the bits. So why call this book "The Pattern in the Stone" if it could just as well have been made of wood and springs?

Chapter 2: Universal Building Blocks
Logical functions and finite state machines. The "Firing Squad Synchronization Problem", which I don't recall ever having heard of before. This problem is an easy one to solve with a pushdown automaton, but hard w/out a stack; I had to look up a solution. TODO: Try implementing it, you can even make it look pretty.

Chapter 3: Programming
Starts out with a quick chat about bugs, the computer that sends threatening letters to all the customers who haven't paid up the $0.00 that they owe. Bugs of this class are constantly being generated every day, through lack of math on the part of programmers. A bad metaphor about the shared understanding between the programmer and the computer. There is none.

Talking to the Computer
I'm a software engineer and I don't really think of myself as talking to the computer. I modify programs, which I expect will be executed. There is a brief chat about Logo; no explicit loops but some recursion. There is a brief comparison of other languages; offering actual insight about there differences. There is a caveat about object-oriented languages which really dates the book, which was published the year I started grad school. The author seems to have thought that all object-oriented languages were used like StarLogo or the newer Greenfoot, chaotically.

Making the Connection
Tries to answer how we get from a Logo program down to the finite state machine with logic of previous chapters. We can think of a chip as a finite state machine with a memory. It goes through several steps as in: read the instruction from the location specified by the PC, execute the operation specified by the instruction, load a new value into the PC. Subroutines are sequences of instructions at an address. They are invoked using the Jump instruction. But now you need a stack to handle the return address. Not just a finite state machine after all! An operating system is just the subroutines that are loaded by default (a pretty reductionist view, but I guess it fits with the simplifications of the rest of the book).

Translating the Language
Very simple, but not wrong explanation of compilers and interpreters. Insists that this is a bit of a continuum, which is the right attitude to take.

Not bad!

Chapter 5: Algorithms and Heuristics
Uses "algorithm" to mean "algorithm that produces and exact answer", uses "heuristic" to mean "algorithm that produces a probably pretty good answer by means of an heuristic".

The Algorithmic Guarantee
About computational complexity and NP-complete problems. The traveling salesman is an example of an NP-complete problem.

Settling for Almost Always
Discussion of game-playing algorithms, which may work by defining a function which scores any particular arrangement of pieces and then explores the solution space to a set depth, expecting the opponent to choose what the computer considers the best move according to its function. I did some of this in my AI class years ago.

Fitness Landscapes
Searching a solution space using heuristics.… (plus d'informations)