Description
Book SynopsisWritten for any motivated reader with a high-school knowledge of mathematics, and the discipline to follow logical arguments, this book presents the proofs for revolutionary impossibility theorems in an accessible way, with less jargon and notation, and more background, intuition, examples, explanations, and exercises.
Trade Review'This unique and lovely book takes us on a grand tour of the limitations of science, mathematics, and of reason itself. To appreciate what is possible we must know the impossible, and such limitations define the boundary between the two. Gusfield offers well-explained gems illustrating various limitations, showing why they arise, giving their historical context, and in contrast to other similar books for a broad audience, presenting rigorous proofs requiring limited background.' Michael Sipser, MIT
'There are impossible problems in many different fields (e.g., Physics, Mathematics). This book is an excellent exposition of these difference ways a problem can be impossible. Along the way, the reader will pick up the needed background which is interesting in itself.' William Gasarch, University of Maryland
Table of ContentsPreface; 1. Yes you can prove a negative!; 2. Bell's impossibility theorem(s); 3. Enjoying Bell magic; 4. Arrow's (and friends') impossibility theorems; 5. Clustering and impossibility; 6. Gödel-ish impossibility; 7. Turing undecidability and incompleteness; 8. Chaitin's theorem: More devastating; 9. Gödel (for real, this time).
