This is a popular science book about what is beyond the ability of reason to know. By "reason" Yanofsky means anything using exact thought like math, logic, computers, physics and even a little philosophy. Questions of what human beings can know is part of a branch of philosophy called epistemology. Such philosophers usually talk about the theories of Lock, Berkley, Hume, Kant etc. In this book, the field is updated and scientific epistemology is discussed. There are many modern results that show that there are objects, that cannot exist, calculations that cannot be performed, and problems that cannot be solved. The book weaves a beautiful tapestry together and shows that many of these limitations in different fields are of the same form.
As a computer professional, I was naturally most interested in the two chapters about limitations of computers. Chapter 5 is about problems that can theoretically be solved but in fact, for any reasonable sized inputs will not be solved for trillions of centuries. The core of the chapter is the idea of NP-Complete problems such as Satisfiability (SAT) or the Traveling Salesperson Problem (TSP). One usually thinks of TSP as a hard computer problem that you can explain to any child, but Yanofsky stresses TSP as a limitation of human knowledge. He explains why most people believe there does not exist a simple algorithms for such problems. Yanofsky finishes this chapter off with a discussion of approximation algorithms and problems that are even harder than NP-Complete problems.
Chapter 6 is not about hard computer problems (complexity theory) but impossible computer problems (computability theory). The classic example is Turing's Halting Problem. There does not exist a program that can tell for any given program and any given input if the program with that input will halt or go into an infinite loop. The chapter also discusses some other unsolvable computer problem and shows how they are connected. There is a discussion of Turing's oracle idea and how this classifies all unsolvable problems. The chapters ends with a short (too short) and inconclusive discussion of whether humans — as opposed to computers — can solve such problems (is AI possible?)
The rest of the book deal with other types of limitations. Chapter 2 discusses limitations of language. Chapter 3 mentions some classical philosophical issues like Zeno's paradoxes and the topic of vagueness. Chapter 4 discusses the counterintuitive notions of infinity and the fact that there are different levels of infinity. Chapter 7 is about three fields of physics: chaos theory, quantum theory, and relativity theory. Chapter 8 deals with philosophy of science issues. Chapter 9 talks about some limitations of mathematics including some basic math problems that a computer (and a human?) can never solve. The chapters of the book are for the most part independent which makes it easier for the reader to read topics that interests her. Chapter 10 summarizes the whole book.
The section on quantum theory deserves special mention. Yanofsky spends 38 pages describing the world of quantum mechanics. But rather than telling the life stories of the founders of quantum theory (too easy, too boring) or trying to teach the math behind quantum theory (too hard), Yanofsky goes through seven or eight experiments in quantum theory and tells us what the results of the experiments show about the universe and our knowledge of the universe. Included in this is the mysterious topic of entanglement and Bell's famous inequality. I had to read that part twice but I can proudly say that I understand it now.
After reading the whole book, my favorite part is the last chapter. Here everything magically comes together in an amazing way. In the first part of the chapter, Yanofsky gives a four-part classification of all the limitations discussed in the book. Within this classification he makes fascinating links between various limitations in different areas. He connects NP-Complete problems and the butterfly effect; the Halting Problem and the barber paradox; language paradoxes and mathematical limitations. From this "high" point of view, all the different limitations fit together perfectly and one can clearly see the whole beautiful landscape.
One of the central ideas in the book is the concept of self-referential paradox. This is a paradox that comes about from a system that can talk about itself. In chapter 2, the liar paradox is shown to come about because English sentences can talk about English sentences. In chapter 3, there is a discussion of time-travel paradoxes (as in the Back to the Future movies) which come about because events that happen because time traveler can make events that affect themselves. Turing's Halting Problem is shown to come about from the fact that programs deal with programs (as operating systems do.) And Gödel's famous Incompleteness Theorems comes from that fact that mathematics can talk about itself. These are just a few of the more famous self-referential paradoxes mentioned in the book. They form a thread that shows that the same scheme of reason is playing a role in many different areas.
There are some philosophical parts of the book that I cannot truly judge. In chapter 3 there is discussion about the problem of identity (to what extent is something the same even when it changes) and the problem of personal identity (to what extent is someone the same even when they change? What makes a human being a human being?) In chapter 8 there is a discussion of the problem of induction; the "unreasonable effectiveness of mathematics" and the anthropic principle. In these philosophical parts of the book, Yanofsky makes some cogent arguments about different issues. Not all his arguments are totally convincing. I like the more scientific and technical parts of the book where it is easy to tell who is right and who is wrong.
I must mention Yanofsky's style. The writing is crisp and totally clear. Although I learned about the Halting Problem when I was in school, I never truly understood Turing's proof of why no computer can ever solve the Halting Problem till I read Yanofsky's proof. There are also some very helpful charts and diagrams. There are a few Venn diagrams that show different classifications. The book is also very funny. There is a sprinkling of some very clever lines that make it a pleasure to read. The footnotes are also full of such hilarious gems.
A coworker told me that this does not surprise him since he read a textbook coauthored by Yanofsky titled Quantum Computing for Computer Science. My coworker said that it was the only book on quantum computing that one can read without a PhD in physics. He said that book was also very clear.
This book is not hard to read. It is beautifully written in a very understandable way. The reason why the book is fascinating is because it has so many diverse topics. And yet, Yanofsky manages to connect all the topics. This book will get you to think about what we can know about the universe in a totally new and exciting way."
Link to Original Source