Table of Contents

1. Atoms and the void; 2. Sets; 3. Gödel, Turing, and friends; 4. Minds and machines; 5. Paleocomplexity; 6. P, NP, and friends; 7. Randomness; 8. Crypto; 9. Quantum; 10. Quantum computing; 11. Penrose; 12. Decoherence and hidden variables; 13. Proofs; 14. How big are quantum states?; 15. Skepticism of quantum computing; 16. Learning; 17. Interactive proofs and more; 18. Fun with the Anthropic Principle; 19. Free will; 20. Time travel; 21. Cosmology and complexity; 22. Ask me anything.

Promotional Information

Takes students and researchers on a tour through some of the deepest ideas of maths, computer science and physics.

About the Author

Scott Aaronson is an Associate Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. Considered one of the top quantum complexity theorists in the world, he is well known for both his research in quantum computing and computational complexity theory and for his widely read blog Shtetl-Optimized. Professor Aaronson also created Complexity Zoo, an online encyclopedia of computational complexity theory and has written popular articles for Scientific American and The New York Times. His research and popular writing have earned him numerous awards, including the United States Presidential Early Career Award for Scientists and Engineers and the Alan T. Waterman Award.

Reviews

'Scott Aaronson has written a beautiful and highly original synthesis of what we know about some of the most fundamental questions in science: what is information? What does it mean to compute? What is the nature of mind and of free will? Highly recommended.' Michael Nielsen, author of Reinventing Discovery

'I laughed, I cried, I fell off my chair - and that was just reading the chapter on computational complexity. Aaronson is a tornado of intellectual activity: he rips our brains from their intellectual foundations; twists them through a tour of physics, mathematics, computer science, and philosophy; stuffs them full of facts and theorems; tickles them until they cry 'Uncle'; and then drops them, quivering, back into our skulls. [He] raises deep questions of how the physical universe is put together and why it is put together the way it is. While we read his lucid explanations we can believe - at least while we hold the book in our hands - that we understand the answers, too.' Seth Lloyd, Massachusetts Institute of Technology and author of Programming the Universe

'Not since Richard Feynman's Lectures on Physics has there been a set of lecture notes as brilliant and as entertaining. Aaronson leads the reader on a wild romp through the most important intellectual achievements in computing and physics, weaving these seemingly disparate fields into a captivating narrative for our modern age of information. [He] wildly runs through the fields of physics and computers, showing us how they are connected, how to understand our computational universe, and what questions exist on the borders of these fields that we still don't understand. This book is a poem disguised as a set of lecture notes. The lectures are on computing and physics, complexity theory and mathematical logic and quantum physics. The poem is made up of proofs, jokes, stories, and revelations, synthesizing the two towering fields of computer science and physics into a coherent tapestry of sheer intellectual awesomeness.' Dave Bacon, Google

'… how can I adequately convey the scope, erudition, virtuosity, panache, hilarity, the unabashed nerdiness, pugnacity, the overwhelming exuberance, the relentless good humor, the biting sarcasm, the coolness and, yes, the intellectual depth of this book?' SIGACT News

'It is the very definition of a Big Ideas Book … It's targeted to readers with a reasonably strong grounding in physics, so it's not exactly a light read, despite Aaronson's trademark breezy writing style. But for those with sufficient background, or the patience to stick with the discussion, the rewards will be great.' Sean Carroll and Jennifer Ouellette, Cocktail Party Physics, Scientific American blog

'The range of subjects covered is immense: set theory, Turing machines, the P versus NP problem, randomness, quantum computing, the hidden variables theory, the anthropic principle, free will, and time travel and complexity. For every one of these diverse topics, the author has something insightful and thought provoking to say. Naturally, this is not a book that can be read quickly, and it is definitely worth repeated reading. The work will make readers think about a lot of subjects and enjoy thinking about them. It definitely belongs in all libraries, especially those serving general readers or students and practitioners of computer science or philosophy. Highly recommended.' R. Bharath, Choice

'… lively, casual, and clearly informed by the author's own important work … stimulating … It should prove valuable to anyone interested in computational complexity, quantum mechanics, and the theory of quantum computing.' Francis Sullivan, Physics Today

'Deep and important.' Times Higher Education

'… a wonderful, personal exploration of topics in theory of computation, complexity theory, physics, and philosophy. His witty, informal writing style makes the material approachable as he weaves together threads of complexity theory, computing theory, mathematical logic, and the math and physics of quantum mechanics (QM) and quantum computing to show how these topics interrelate to each other, what that says about the universe, and something about us … this book is a treat.' G. R. Mayforth, Computing Reviews