Proven Impossible: Elementary Proofs of Profound Impossibility from Arrow, Bell, Chaitin, Gödel, Turing...

— —

Dan Gusfield (University of California, Davis)

Proven Impossible

Elementary Proofs of Profound Impossibility from Arrow, Bell, Chaitin, Gödel, Turing and More...

Dan Gusfield (University of California, Davis)

$245.95 $196.46

Hardback

Not in-store but you can order this
How long will it take?

Availability Information

We source books from suppliers in Australia and overseas. For books we don't currently have in stock, the time it takes to get them from our suppliers can vary widely - from a few days to a few months - so we check each book with each supplier to determine the expected time it will take to be supplied to us.

We then advise you accordingly. If the time taken to get any book is too long for you, you can let us know and we will cancel or adjust your order, and refund as required.

To find out the anticipated arrival time for specific items prior to ordering, please contact us by phone or email:

Phone +61 2 9264 3111, or 1800 4 BOOKS (1800 4 26657) if outside Sydney:
option 1 Abbey's Bookshop (Crime, History, Science, Kids & more) • info@abbeys.com.au
option 2 Language Book Centre (ESL & Foreign Languages) • language@abbeys.com.au
option 3 Galaxy Bookshop (Sci-fi, Fantasy, Romance, Graphic Novels) • sf@galaxybooks.com.au

QTY:

English

Cambridge University Press
18 January 2024

Applied mathematics; Algorithms & data structures; Maths for computer scientists; Computer architecture & logic design

In mathematics, it simply is not true that 'you can't prove a negative'. Many revolutionary impossibility theorems reveal profound properties of logic, computation, fairness and the universe, and form the mathematical background of new technologies and Nobel prizes. But to fully appreciate these theorems and their impact on mathematics and beyond, you must understand their proofs. This book is the first to present these proofs for a broad, lay audience. It fully develops the simplest rigorous proofs found in the literature, reworked to contain less jargon and notation, and more background, intuition, examples, explanations, and exercises. Amazingly, all of the proofs in this book involve only arithmetic and basic logic – and are elementary, starting only from first principles and definitions. Very little background knowledge is required, and no specialized mathematical training – all you need is the discipline to follow logical arguments and a pen in your hand.

By: Dan Gusfield (University of California Davis)
Imprint: Cambridge University Press
Country of Publication: United Kingdom
Dimensions: Height: 229mm, Width: 152mm, Spine: 19mm
Weight: 504g
ISBN: 9781009349505
ISBN 10: 1009349503
Pages: 270
Publication Date: 18 January 2024
Audience: General/trade , ELT Advanced
Format: Hardback
Publisher's Status: Active

Preface; 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).

Dan Gusfield is Distinguished Professor emeritus, and former department chair, in the Computer Science Department at University of California, Davis. He is a Fellow of the ACM, the IEEE, and the ISCB. His previous books are 'The Stable Marriage Problem' (1989, co-authored with Rob Irving); 'Strings, Trees and Sequences' (1997); 'ReCombinatorics' (2014); and 'Integer Linear Programming in Computational and Systems Biology' (2019). As this book reflects, his teaching emphasized mathematical rigor as well as accessibility and clarity. He produced over 100 hours of video lectures on a wide range of topics, now viewed over a million times on the web.

Reviews for Proven Impossible: Elementary Proofs of Profound Impossibility from Arrow, Bell, Chaitin, Gödel, Turing and More

'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