December 1, 2012 12:12 AM Subscribe

The Nature of Computation - Intellects Vast and Warm and Sympathetic: "I hand you a network or graph, and ask whether there is a path through the network that crosses each edge exactly once, returning to its starting point. (That is, I ask whether there is a 'Eulerian' cycle.) Then I hand you another network, and ask whether there is a path which visits each node exactly once. (That is, I ask whether there is a 'Hamiltonian' cycle.) How hard is it to answer me?" (via)
posted by kliuless (19 comments total)
97 users marked this as a favorite

This is, simply put, the best-written book on the theory of computation I have ever read; one of the best-written mathematical books I have ever read, period... from beginning to end, and all the 900+ pages in between, this was lucid, insightful, just rigorous enough, alive to how technical problems relate to larger issues, and above all, passionate and human.also btw...

- On the origin of probability in quantum mechanics - "Because the wave function evolves entirely deterministically in many worlds, all probabilities are necessarily subjective and the interpretation does not require true randomness, thereby preserving Einstein's requirement that outcomes have causes."
- The Mathematical Origin of Irreversibility - "The key to this rather profound connection resides in a universal property of Markov processes discovered recently in the context of non-equilibrium statistical mechanics, and known as the 'fluctuation theorem'. Typically stated in terms of 'dissipated work' or 'entropy production', this result can be seen as an extension of the Second Law of Thermodynamics to
*small*systems, where thermal fluctuations cannot be neglected. But*it is actually much more than this*: it is the mathematical underpinning of irreversibility itself, be it thermodynamical, evolutionary, or else. To make this point clear, let me start by giving a general formulation of the fluctuation theorem that makes no reference to physics concepts such as 'heat' or 'work' " - A nice easy explanation of the abc conjecture [also btw 1,2,3,4,5,6,7,8]
- An argument for the reality of mathematical entities [1,2,3]
- From Particles to People: The Laws of Nature and the Meaning of Life [1,2,3,4,5]

Oo. I love this stuff, will have to come back and read everything when I have more time.

In a similar vein, 'The Computational Beauty of Nature' is also a fascinating read & a deep dive into the links between computation, chaos theory and order.

(First link is to a friend of mine: Hi Danny!)

posted by pharm at 12:49 AM on December 1, 2012

In a similar vein, 'The Computational Beauty of Nature' is also a fascinating read & a deep dive into the links between computation, chaos theory and order.

(First link is to a friend of mine: Hi Danny!)

posted by pharm at 12:49 AM on December 1, 2012

Isn't 1032 pages rather long though? Algorithms text books are commonly that long, but not textbooks on complexity. I once tried teaching complexity theory using another book besides Sipser's *Introduction to the Theory of Computation*, big mistake. I could imagine huge advantages to focussing less on SAT-like problems and more on integer programming though, especially once you reach approximation algorithms for NP-hard optimization problems.

posted by jeffburdges at 3:31 AM on December 1, 2012 [1 favorite]

posted by jeffburdges at 3:31 AM on December 1, 2012 [1 favorite]

From the second article: *I have no idea why theoretical computer science insists on using a vocabulary ["The Adversary"] which makes it sound like a bad fantasy novel (i.e., the kind I read). Perhaps it's some lingering influence of Norbert Wiener?*

I think it's all of us Jews in computer science. "The Adversary" is a character in the Hebrew bible, a divine servant of God whose job it is to fuck your shit up. He's kind of the enforcer of Murphy's Law. In the book of Job, God sends The Adversary to present Job with the worst possible sequence of events at the worst possible times, so that all of his coping strategies fail. That pretty well matches how it works in the theory of algorithms. (In Hebrew, The Adversary's name is*Satan*, and the Christians promoted him to a whole different job.)

posted by Harvey Kilobit at 4:27 AM on December 1, 2012 [11 favorites]

I think it's all of us Jews in computer science. "The Adversary" is a character in the Hebrew bible, a divine servant of God whose job it is to fuck your shit up. He's kind of the enforcer of Murphy's Law. In the book of Job, God sends The Adversary to present Job with the worst possible sequence of events at the worst possible times, so that all of his coping strategies fail. That pretty well matches how it works in the theory of algorithms. (In Hebrew, The Adversary's name is

posted by Harvey Kilobit at 4:27 AM on December 1, 2012 [11 favorites]

Pretty fascinating, however I think I'll wait for the abridged version...

posted by SounderCoo at 7:14 AM on December 1, 2012

posted by SounderCoo at 7:14 AM on December 1, 2012

The Metafilter front page **really** needs to list favorites counts for posts, not just comments counts. I wonder how many other posts of the "fascinating topic that people don't feel qualified to talk about" category I've missed because I don't have time to do more than skim the front page for public interest levels, and with a handful of comments these wonderful posts end up indistinguishable from the much more common "topic that people don't care to talk about" category.

posted by roystgnr at 7:49 AM on December 1, 2012 [1 favorite]

posted by roystgnr at 7:49 AM on December 1, 2012 [1 favorite]

yeah, it definitely should have been truncated to 1024, or expanded to 2048 so the other pages didn't get wasted

wait, algorithms books are limited to power of 2 sizes, right?

posted by idiopath at 8:12 AM on December 1, 2012 [8 favorites]

You're confusing algorithms with computer architecture. All alignment issues disappear into the constant factor in big O notation.

posted by jeffburdges at 9:00 AM on December 1, 2012 [6 favorites]

posted by jeffburdges at 9:00 AM on December 1, 2012 [6 favorites]

Great reading for the weekend!

Had a conversation in a bar tonight that covered many of the topics in these links; usually a sign that we've (I've) had a few too many...

posted by jet_manifesto at 9:44 AM on December 1, 2012

Had a conversation in a bar tonight that covered many of the topics in these links; usually a sign that we've (I've) had a few too many...

posted by jet_manifesto at 9:44 AM on December 1, 2012

Between this and the *My Little Pony* AI Singularity post, I'm going to have to drag out my old notebooks and get to work.

posted by ob1quixote at 11:05 AM on December 1, 2012

posted by ob1quixote at 11:05 AM on December 1, 2012

Pretty fascinating, however I think I'll wait for the abridged version...

I'd love to have a joke account under the name 'Kolmogorov', and post as a response "Sorry, that's the shortest possible."

posted by benito.strauss at 11:50 AM on December 1, 2012 [2 favorites]

I'd love to have a joke account under the name 'Kolmogorov', and post as a response "Sorry, that's the shortest possible."

posted by benito.strauss at 11:50 AM on December 1, 2012 [2 favorites]

"*don't you know I have things to do!?!*

posted by Algebra at 9:32 on December 1 [+] [!]"

the field of algorithms decides exactly which work you have to do, Algebra

posted by idiopath at 12:00 PM on December 1, 2012 [2 favorites]

posted by Algebra at 9:32 on December 1 [+] [!]

the field of algorithms decides exactly which work you have to do, Algebra

posted by idiopath at 12:00 PM on December 1, 2012 [2 favorites]

TNOC is quite long, but the first third or so - under 400 pages - could be read by itself. I've suggested to the authors and publisher that that be published separately, ideally as a paperback.

posted by danny3 at 10:29 AM on December 2, 2012

posted by danny3 at 10:29 AM on December 2, 2012

John Von Neumann Documentary - "Teller on von Neumann's enjoyment of thinking, and his horror at the breakdown of this ability due to his terminal cancer. (Also mention's that vN's relation to 'the rest of us' was similar to talking to a 3 year old :-)"

The simulated brain! "First computer model to produce complex behaviour performs almost as well as humans at simple number tasks."

posted by kliuless at 9:00 PM on December 2, 2012 [3 favorites]

The simulated brain! "First computer model to produce complex behaviour performs almost as well as humans at simple number tasks."

posted by kliuless at 9:00 PM on December 2, 2012 [3 favorites]

The library at work (woo!) at this book. I'm only 27 pages in and it's pretty fantastic so far. There are 1000 pages, but I think if I'm still loving it around 100-200 pages, I'm buying a copy. Thanks for the tip!

posted by DU at 4:10 AM on December 20, 2012

posted by DU at 4:10 AM on December 20, 2012

Measurement: Exploring the Whimsy of Math through Playful Patterns, Shape and Motion

posted by kliuless at 11:41 PM on December 26, 2012

posted by kliuless at 11:41 PM on December 26, 2012

« Older December 1st is World AIDS Day... | What adults may remember best ... Newer »

This thread has been archived and is closed to new comments

posted by kellybird at 12:36 AM on December 1, 2012 [2 favorites]