28

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?

Please have some description about why the book would be nice.

Community
  • 1
Subhayan
  • 831
  • 9
  • 19
  • 1
    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). – Marzio De Biasi Sep 13 '13 at 19:40
  • 3
    @MarzioDeBiasi http://en.wikipedia.org/wiki/Popular_science – Sasho Nikolov Sep 13 '13 at 20:27
  • 4
    I think the question should be community wiki. – Boris Bukh Sep 14 '13 at 00:00
  • not phrased so specifically however a reasonable angle is "nontechnical books that inspire people to further learn/study TCS" – vzn Sep 14 '13 at 02:15
  • 2
    I think non-technical, easily accessible are the good keywords here. – Subhayan Sep 14 '13 at 02:37
  • 2
    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

12 Answers12

24

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.

Artem Kaznatcheev
  • 10,251
  • 12
  • 74
  • 174
Aaron Roth
  • 9,870
  • 1
  • 43
  • 68
  • 1
    Definitely true. – Giorgio Camerani Sep 18 '13 at 21:26
  • 9
    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. – Jeffε Sep 19 '13 at 03:17
  • 6
    "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 – Vijay D Sep 19 '13 at 07:02
  • 1
    You will have hard time finding an expert in the topics discussed in the book (e.g. logic) who would say anything positive about it. Popular inspiring books are not necessarily good books. – Kaveh Sep 19 '13 at 16:58
  • 3
    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. – Vijay D Sep 20 '13 at 05:56
  • see also learning Godel, Escher, Bach still valid today? programmers.se – vzn Sep 20 '13 at 18:20
  • 5
    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. – Artem Kaznatcheev Sep 20 '13 at 20:22
16

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.

Addendum

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

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • Upvoted just for Martin Gardner. I first learned about RSA from Mathematical Games, which has influenced my career since then. – nealmcb Sep 26 '16 at 02:23
14

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.

user774025
  • 291
  • 1
  • 7
7

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.

Artem Kaznatcheev
  • 10,251
  • 12
  • 74
  • 174
6

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.

zodiac
  • 131
  • 3
6

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

Martin Schröder
  • 103
  • 9
efutch
  • 11
  • 1
  • 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! – nealmcb Sep 26 '16 at 02:24
5

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

David Richerby
  • 2,765
  • 2
  • 18
  • 28
  • 1
    My understanding on "inspire" is that the books should predate the development of TCS. – Yixin Cao Sep 13 '13 at 20:46
  • 6
    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? – David Richerby Sep 13 '13 at 20:56
5

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.

László Kozma
  • 1,336
  • 1
  • 10
  • 16
2

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.

JRN
  • 127
  • 1
  • 1
  • 8
  • 3
    Are you aware that Wolfram is a little bit "controversial" among computer scientists? – Marcos Villagra Sep 15 '13 at 13:55
  • Thank you for the comment. My primary field of study is not computer science, so I didn't know that the book was controversial. Do you think I should delete this answer? – JRN Sep 15 '13 at 13:57
  • 1
    imho wolframs research is very original, pioneering, worthwhile, and influential albeit unconventional/unorthodox and out-of-mainstream in places, have cited it myself here several times with similarly lukewarm reception. there are many reasons thrown around for why it is "controversial" [agreed to some degree] but not all of them valid. MV think you should provide a ref. otherwise its just unsubstantiated off-the-record gossip. one questionable reason appears to be that its too empirical. also, wolframs bkg is physics. maybe a topic for meta. – vzn Sep 15 '13 at 16:21
  • 6
    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: http://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.) – Joshua Grochow Sep 16 '13 at 19:14
  • @JoshuaGrochow, thanks for the link and the suggestion. – JRN Sep 17 '13 at 00:20
  • 15
    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. – Jeffε Sep 17 '13 at 00:39
  • 4
    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. – Vijay D Sep 18 '13 at 22:04
  • 2
    @VijayD, thanks for the kind words. I understand the downvotes and I initially wanted to delete the answer when I realized that it might cause controversy. I'm keeping the answer up because I think it would be rude to the many who have commented if I deleted it. I don't want to "fan the flames" so I will refrain from making additional comments about the book. Thanks again. – JRN Sep 18 '13 at 23:28
  • 2
    @JoelReyesNoche, you have my sympathies. I would imagine that the downvotes (not me) are targeted at Wolfram and not you. It may help if you added in your answer that you are not a computer scientist. I am still curious though: What did the book inspire you to do, or think of, or work on? – Vijay D Sep 19 '13 at 00:27
  • 1
    @JoelReyesNoche, my original comment was simply to let you know what's the stance of most CS researches about that book in particular. VijayD put it very well, if that is what inspired you that's fine, and that makes it a valid answer. I didn't downvoted the question, but I won't upvote it neither. – Marcos Villagra Sep 19 '13 at 01:51
  • 2
    I also think this is a perfectly fine answer. (I'm not one of the downvoters.) But just as with GEB, don't mistake the inspiration for real substance. – Jeffε Sep 19 '13 at 03:16
  • 3
    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. – JRN Sep 19 '13 at 09:31
  • 1
    @JoelReyesNoche. That's a fantastic story! Please, please add it to your answer. As Masters student my background was circuit design, but working on a hybrid systems problem led me to the Thue-Morse sequence, so I did my Masters project on automata theory. – Vijay D Sep 19 '13 at 16:17
  • 1
    see also recent economist profile, wolfram. also wikipedia has good overview – vzn Sep 19 '13 at 17:08
  • In my previous comment, I should have said "that did not repeat thrice." @VijayD, I don't want to edit the answer because I don't want to bump it up. I think the comment is enough. More details can be found here. I also used to do circuit design (computer arithmetic) but now my interests are elsewhere. – JRN Sep 20 '13 at 00:17
2

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

042
  • 270
  • 1
  • 7
1

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.

akr_
  • 101
  • 3
0

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:

vzn
  • 11,014
  • 2
  • 31
  • 64