# What are the popular science books that inspire TCS?

There is a reputation, that in computer science, we do not have popular science books. Of course that's not really true!

(In the same spirit of list of What Books Should Everyone Read?, What papers should everyone read?, What videos should everybody watch? and inspired from Favorite popular math book)

What are the popular science books or resources that inspire CS Theory?

• What do you mean with "popular"? "popular" among TCS reasearchers/community? (something like the book: Michael Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness)? Or popular among common people (in this case I think that it is unlikely to be a "resource that inspires" a CS theory). Sep 13 '13 at 19:40
• @MarzioDeBiasi en.wikipedia.org/wiki/Popular_science Sep 13 '13 at 20:27
• I think the question should be community wiki. Sep 14 '13 at 0:00
• I think non-technical, easily accessible are the good keywords here. Sep 14 '13 at 2:37
• Brian Hayes is an outstanding/award-winning writer/popularizer of (T)CS-related topics (esp intersecting with mathematics) in his column Computing Science for American Scientist magazine, most of which are available online, but the TCS-focused elements not compiled into a book (yet?). blogging at "bit-player".
– vzn
Sep 17 '13 at 17:35

I know of many theoretical computer scientists whose first inspiration came from reading Godel, Escher, Bach

Its becoming a bit dated at this point, but is still an excellent read.

• Definitely true. Sep 18 '13 at 21:26
• Yeah, but. Back when I was a graduate student, one of the local AI faculty told me his secret for selecting good PhD students from the applicant pool. If an applicant's statement of purpose mentioned Gödel, Escher, Bach, he rejected them. Sep 19 '13 at 3:17
• "hail Goedel as the greatest logician of all time, mount the absurdities of Goedel numbering on a pin, and make it a sort of super-puzzle. This burying-under-flowers is characteristic of that monument of vulgarity, "Goedel, Escher, Bach"." -- Jean Yves Girard Sep 19 '13 at 7:02
• I think in this case, as in many cases with popular science books that experts dislike, the author is not an expert in the field and takes the liberty of interpreting and presenting results in a way that an expert in the field never would. Sep 20 '13 at 5:56
• I read GEB before I knew any cstheory, and found it inspirational. In the long run, though, the only real thing I learnt from it is how to write in a way that captures the popular imagination. However, this is a very important lesson. I've recently read one of Hofstadter's other books (I Am a Strange Loop) and was overwhelmed by how poor his scholarship is (never acknowledging earlier philosophers when he blatantly steals ideas from them). It made me sad to know that one of the easiest way to a cult following is do this. I would never reread GEB, since it would ruin my earlier experience. Sep 20 '13 at 20:22

After clarifying the (unclear for me) meaning of "popular science" (thanks Sasho :-) I propose:

Title: Winning Ways for Your Mathematical Plays (4 volumes)

Authors: Elwyn R. Berlekamp, John H. Conway, Richard K. Guy

Description: it can be considered a compendium of information on mathematical games (tons of games are analyzed: coin and paper-and-pencil games, Soma, Rubik's Cube, mechanical wire and string puzzles, sliding block puzzles, magic squares, Life). It is easy enough to please any fan of recreational mathematics or simply anyone who is interested in games and how to play them well; but I think that it has also been a source of inspiration for many deeper results in combinatorial game theory.

It is not a book, but I think that the Martin Gardner's 'Mathematical Games and Recreations' column for Scientific American must be cited.

Resource: The 'Mathematical Games and Recreations' column for Scientific American

Author: Martin Gardner

Description: for 25 of his 95 years, Martin Gardner wrote 'Mathematical Games and Recreations', a monthly column for Scientific American magazine. These columns have inspired hundreds of thousands of readers to delve more deeply into the large world of mathematics. He has also made significant contributions to magic, philosophy, debunking pseudoscience, and children's literature. Many Martin Gardner's books are collections of informative extracts from his Scientific American column (e.g. Fractal Music, Hypercards and More...: Mathematical Recreations from Scientific American Magazine, Wheels, Life and Other Mathematical Amusements, ecc. ecc.).

• Upvoted just for Martin Gardner. I first learned about RSA from Mathematical Games, which has influenced my career since then. Sep 26 '16 at 2:23

Scott Aaronson's Quantum Computing Since Democritus. This book is an excellent introduction to theoretical computer science and quantum computing for layman as well as begining students of theoretical computer science. Unlike other pop science books this book is rigorous as well.

At the intersection of evolutionary biology and theoretical computer science there are two recent books.

• Valiant's "Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World", and

• Chaitin's "Proving Darwin: Making Biology Mathematical".

Both books look at evolution through the algorithmic lens, with the first concentrating on how evolution, learning, and intelligence can be all expressed in the PAC-framework of Machine Learning. The second book, looks at how to build a toy model of evolutionary innovation using algorithmic information theory. Although the books are only loosely connected to biology, they do present computer science in a standard pop-sci way and show how it related to more common topics in pop-sci, like evolution.

• fresh NYT review of Valiant
– vzn
Oct 3 '13 at 23:14

I first got interested in TCS after reading Scott Aaronson's writings; one of the earlier ones was Who Can Name the Bigger Number?, which does have a pop-science feel to it

Another very good one I read later is Why Philosophers Should Care About Computational Complexity; although written in an academic style I would say it is "popular science" in that its audience includes philosophers who have no previous experience with TCS.

IMHO, I would recommend these "popular" books:

1. Any book by James Gleick - Chaos, The Information
2. Fire in the Valley, for an account of early PC history
3. Books by Steven Levy: Insanely Great, In the Plex, Hackers, etc.

And the grand master, though somewhat dated:

The Soul of a New Machine by Tracy Kidder

• was thinking of adding the Kidder ref myself [famous, influential, & like it] but decided against it based on the rigorous audience here. its interesting to note a kind of shift in what constitutes TCS over time based on advances in theory. Soul of New Machine published in 1981 probably was much closer to being regarded as cutting edge TCS at the time given how relatively new microprocessors were. today, CPU design, less so, much more prosaic/"applied". therefore, theres a "moving the goalposts over time/complexity inflation" aspect to TCS which that ref reveals somewhat.
– vzn
Sep 20 '13 at 18:10
• Yes - Gleick's The Information is excellent! Sep 26 '16 at 2:24

The obvious answer would be Lance Fortnow's book The Golden Ticket but I can't say anything more about it, as I've not read it myself. (If somebody has read it and wants to say more, please leave a separate answer and I'll delete this one.)

• My understanding on "inspire" is that the books should predate the development of TCS. Sep 13 '13 at 20:46
• That interpretation leads to an extremely narrow question. Why would one expect a popular science book from outside TCS to have inspired TCS in that sense? Sep 13 '13 at 20:56

I liked:

Charles Petzold: The Annotated Turing, which is essentially a guide through Turing's seminal paper and a set of notes explaining things.

I also liked:

Douglas Hofstadter: Metamagical Themas, in my opinion more interesting than GEB (which is - according to some of the other commenters - not too difficult to achieve :) ), this is a collection of his columns in Scientific American, popularising many interesting ideas, although not all CS-related, obviously.

As a proper CS popular book, many people seem to like:

A. K. Dewdney: The New Turing Omnibus, although I haven't had the chance to read it.

I was inspired by Stephen Wolfram's A New Kind of Science. If I understand correctly, one of the main themes of the book is that whereas the main tool in science used to be mathematics (in particular, systems of partial differential equations), the main tool will soon be computer science (in particular, cellular automata).

Edit: It has been pointed out in the comments below that the book is controversial. I quote a review by Scott Aaronson:

[W]ere the book more cautious in its claims and more willing to acknowledge previous work, it would likely be easier for readers to assess what it does offer: a cellular-automaton-based perspective on existing ideas in science.

• Are you aware that Wolfram is a little bit "controversial" among computer scientists? Sep 15 '13 at 13:55
• I would leave the answer up, as if the book inspires people to learn more about TCS etc. then I think that counts, whether or not its controversial (by analogy, think about how many inspiring yet controversial books there are about evolution...). See Aaronson's review for some of the technical claims: arxiv.org/abs/quant-ph/0206089. (If you're still uncomfortable with keeping it up, you could keep the answer but add a note that some view it as controversial.) Sep 16 '13 at 19:14
• imho wolframs research is very original, pioneering, worthwhile, and influential — I feel exactly the opposite, on all counts. Wolfram takes credit for, ignores, and or dismisses other people's prior work; he emphasizes trivial points while missing larger ones; his generalizations to traditional science are quickly dismissed as obviously wrong. His book should have been entitled A New (Kind of) Science. Sep 17 '13 at 0:39
• I think this is a perfectly fine answer. If Joel says it inspired him, then there is no questioning that. Joel, I think you could also add a bit more of a retrospective, if you can, of how you think of the book once you became a scientist. Sep 18 '13 at 22:04
• Thanks for the comments. @VijayD, as an electrical engineer, I became interested in randomness. I discovered an infinite binary sequence that did not repeat, and it was through NKS that I discovered that it was already known as the Thue-Morse sequence. Thus, NKS led me to the field of study known as combinatorics on words. Sep 19 '13 at 9:31

The book Algorithmic Adventures by Hromkovič is a rare attempt to explain some really mainstream ideas of theoretical computer science to a wide audience.

I will suggest the following books.

1. The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow. The book is written for all kind of readers and doesn't require you to know anything about Theoretical Computer Science. It shows the disney world where P=NP.

2. The Nature of Computation by Cristopher Moore and Stephen Mertens. Deep ideas of Theoretical Computer Science persented in an enjoyable way. From Cantor's Argument to complex ideas such as Interactive Proofs and Quantum Computation presentable to all kind of readers irrespective of their backgrounds.

3. The Code Book: The Secrets Behind Codebreaking by Simon Singh. It is an absolutely amazing book on mathematics behind cryptography and suitable for all kind of readers. From usage of cryptography in ancient past to its importance in world war and breaking the enigma. The history of cryptography is presented with great stories behind them. It also describes why the people behind RSA algorithm didn't use their names in alphabetical order as researchers in Theoretical Computer Science usually do.

there are many such references, they seem to be increasing, as some have noted we seem to be in the midst/living through a Golden Age of algorithms. some newer algorithm-focused refs [hence not so well known] not listed so far that may be interesting, some written by TCS researchers/scientists/experts (Cormen, Valiant, Davis), others by popsci writers:

also, other interesting topics from news/headlines with a strong overlap between TCS and popular science writing/books:

• quantum computing
• high frequency trading ("HFT"). this is a strong mix between theory and applied and uses advanced machine learning, datamining, statistics, and mathematics techniques. [can name some refs on this but suspect this audience will not regard it as "pure" enough so will hold off for now.]
• cryptography
• bioinformatics
• etc!
• Aaronson's and Valiant's books have already been mentioned in their own answers. Have you read all these books? If not, then why are you recommending them? Also, can you explain what bioinformatics has to do with theoretical computer science? I would argue that there is not that much overlap. Similar goes for HFT, although there are some connections. Sep 20 '13 at 20:29
• didnt cite refs on HFT or bioinformatics or the the other topics anticipating objections originating from more narrow views on TCS boundaries (which imho can be quite restrictive here & others have agreed). didnt exactly agree with all your blog [elaborated in comment there] but think youve raised a worthwhile topic for other site questions wrt eg bioinformatics etc. possibly also in meta. see also bioinformatics
– vzn
Sep 20 '13 at 21:59
• addendum, another neat/interesting/recent ref Understanding computation by Stewart/O'Reilly, covers TMs, TM completeness etc using Ruby
– vzn
Sep 21 '13 at 15:56
• see also Think Complexity: Complexity Science and Computational Modeling by Downey/O'Reilly publisher. covers CAs, [small world] graphs, fractals, etc. Python code. influenced by Wolframs NKS.
– vzn
Sep 21 '13 at 16:12
• this ref starts from a more math-oriented angle but has significant TCS coverage eg TMs, $\lambda$-calculus, halting problem etc Good Math: A Geek's Guide to the Beauty of Numbers, Logic, and Computation by Mark C. Chu-Carroll
– vzn
Sep 21 '13 at 16:30