Algorithms from the “Book”

By "woven into the fabric" I mean that the physical world executes what we think of as algorithms, as part of its natural existence. We write an equation that represents viscosity, but nature just executes viscosity because of the way the atoms interact. Or rather, viscosity emerges because of the way things interact. There is no equation, there is no computational organization, there is no unit testing, there's just doing-- at massive scale.

By the way, I would say not all algorithms occur in reality, and when they do, nature isn't necessarily very good at them. For example, sort and binary search just don't seem that high up on the list of things the physical world cares about. The natural sorting process by which dirt in a container separates out into various gradations of size, corresponds to bubble sort-- not an especially efficient algorithm.

In what way is a "discussion on interesting algorithms" not already pseudo-philosophical?

But OK, I'll do it your way:

An interesting class of algorithms is finite-difference approximations [1]. Even more interesting are algorithms for designing such approximations [2]. A key insight to making these algorithms work is that Taylor series approximations can be used to study the truncation errors of discrete approximations to continuous phenomena. However these techniques, by themselves, mainly interest me in the context of the physical problems they are meant to address. Since those problems come from the physical world, I would argue that the algorithms themselves don't satisfy the formal criteria set forth in the original question, of what algorithms god would write down in a book.

[1] See LeVeque, "Finite Difference Methods for Ordinary and Partial Differential Equations".

[2] See Hamming, "Numerical Methods for Scientists and Engineers".

This is part of a series. I haven't read Solve It but there is another one that I worked through several years ago before returning to school, How to Prove It, that really cleared up how to do proofs for me. It is all based around set theory and some of the later proofs are quite deep:

http://www.amazon.com/gp/aw/d/0521675995/

If I recall correctly, this book also comes very highly recommended from Rich Hickey, the author of Clojure.

I ordered the hardcover Proofs a few weeks ago after seeing the Calkin-Wilf tree [1] [2]. I cannot suggest it on the Kindle because you're going to want to write in it—there are even large margins to encourage this kind of behavior.

[1] http://hackage.haskell.org/packages/archive/prelude-safeenum... [2] http://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals...

It's one of the best books I've ever bought measured in raw joy and satisfaction per page. Like all proofs, reading is a very involved process, but these are genuinely stunning ones.

There was a Kindle edition for the 3rd edition of the book, but it was justifiably withdrawn. Here was my review on Amazon to warn people against buying it:

=================

The Kindle edition is completely worthless, because it is missing many symbols. It appears to have been done using OCR, and it was confused by mathematical symbols. For example, there are some places where I THINK it was supposed to be the greek letter phi, but it comes out as a left parenthesis and a right parenthesis. At least with that you can figure out what it was supposed to be. There is much worse--places where symbols are completely gone. E.g., there is a place where you just get a capital sigma with a subscript giving a summation limit, a blank space, a less than sign, and another blank space. So, the proof is saying the some of something is less than something else.

This is a shame, because the book itself, from what I can see, is EXCELLENT.

=================

This illustrates a major annoyance with Amazon's review system. They combine reviews for all formats of a book. This is bad both from the review side and the potential purchaser side.

From the review side, how many stars should I have given the book? The non-Kindle versions are excellent. 5 stars. The Kindle edition, as I said, was completely worthless. 1 star. So do I give 5 stars or 1 star? 3 stars?

From the purchaser side, the combined reviews are annoying because I want to see the reviews specifically for the format I'm considering. For "Proofs from the Book" this is not too much of a problem because there are only 17 reviews. I can just read them all. For books with hundreds of reviews, it is a problem.

As far as math books on Kindle go, PftB is the worst I've tried, but I've not actually found any math book that was acceptable to me. The others I've seen have had all the symbols there, but it was done by having the math handled as embedded images, which did not resize if I changed the font size, and were smaller than the math in the paper book.

True, although this reminds me of an old Von Neumann joke (it was probably a Newton joke once):

A colleague walks up to Von Neumann at a party. "Hey!" he challenges. "Two locomotives are speeding towards each other on a track. They begin ten miles apart and are both travelling at 30mph."

"A fly on the hood of one locomotive flies to the other locomotive at 60mph, then returns to the first, and keeps going back and forth between them until the two crash, killing the fly."

"How far has the fly travelled?"

Von Neumann considers, then gives the correct answer. "It's true," his colleague says, "you can instantly see the insight to any problem. You knew that you could merely sort out how long it takes and then work out the distance from the fly's speed."

Von Neumann frowns. "It seemed simpler to sum the series in hy head, and it's a more general solution."