December 1, 2012 12:12 AM Subscribe
The Nature of Computation
posted by kliuless (19 comments total)
98 users marked this as a favorite
- 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.
Could the Universe Reveal Itself as a Computer Simulation?
- 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]