direct realism

December 1, 2012 12:12 AM

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)

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]

Could the Universe Reveal Itself as a Computer Simulation? (previously)

posted by kliuless (19 comments total)

nice list! If you want more on the ABC conjecture, this is an expository piece by Barry Mazur at Harvard that walks you through the problem's history and why it is important, and how it fits into other related math work like Fermat's last theorem. This piece by Barry Mazur is one of the most clear and beautiful pieces of (expository) math writing I've ever read. He's a very good writer.
posted by kellybird at 12:36 AM on December 1, 2012 [2 favorites]

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

(thanks ;)
posted by kliuless at 1:11 AM on December 1, 2012

That is a wonderful tag list.
posted by Moistener at 1:16 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]

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]

Pretty fascinating, however I think I'll wait for the abridged version...
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]

"Isn't 1032 pages rather long though?"

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]

don't you know I have things to do!?!
posted by Algebra at 9:32 AM on December 1, 2012

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

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

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]

"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]

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

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 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

Measurement: Exploring the Whimsy of Math through Playful Patterns, Shape and Motion
posted by kliuless at 11:41 PM on December 26, 2012