28
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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). $\endgroup$
    – Marzio De Biasi
    Commented Sep 13, 2013 at 19:40
  • 3
    $\begingroup$ @MarzioDeBiasi en.wikipedia.org/wiki/Popular_science $\endgroup$
    – Sasho Nikolov
    Commented Sep 13, 2013 at 20:27
  • 4
    $\begingroup$ I think the question should be community wiki. $\endgroup$
    – Boris Bukh
    Commented Sep 14, 2013 at 0:00
  • 2
    $\begingroup$ I think non-technical, easily accessible are the good keywords here. $\endgroup$
    – Subhayan
    Commented Sep 14, 2013 at 2:37
  • 2
    $\begingroup$ 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". $\endgroup$
    – vzn
    Commented Sep 17, 2013 at 17:35

12 Answers 12

Reset to default
24
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Definitely true. $\endgroup$
    – Giorgio Camerani
    Commented Sep 18, 2013 at 21:26
  • 9
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Commented Sep 19, 2013 at 3:17
  • 6
    $\begingroup$ "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 $\endgroup$
    – Vijay D
    Commented Sep 19, 2013 at 7:02
  • 3
    $\begingroup$ 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. $\endgroup$
    – Vijay D
    Commented Sep 20, 2013 at 5:56
  • 5
    $\begingroup$ 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. $\endgroup$
    – Artem Kaznatcheev ♦
    Commented Sep 20, 2013 at 20:22
16
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Upvoted just for Martin Gardner. I first learned about RSA from Mathematical Games, which has influenced my career since then. $\endgroup$
    – nealmcb
    Commented Sep 26, 2016 at 2:23
14
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ fresh NYT review of Valiant $\endgroup$
    – vzn
    Commented Oct 3, 2013 at 23:14
6
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Commented Sep 20, 2013 at 18:10
  • $\begingroup$ Yes - Gleick's The Information is excellent! $\endgroup$
    – nealmcb
    Commented Sep 26, 2016 at 2:24
5
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ My understanding on "inspire" is that the books should predate the development of TCS. $\endgroup$
    – Yixin Cao
    Commented Sep 13, 2013 at 20:46
  • 6
    $\begingroup$ 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? $\endgroup$
    – David Richerby
    Commented Sep 13, 2013 at 20:56
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
15
  • 3
    $\begingroup$ Are you aware that Wolfram is a little bit "controversial" among computer scientists? $\endgroup$
    – Marcos Villagra
    Commented Sep 15, 2013 at 13:55
  • 6
    $\begingroup$ 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.) $\endgroup$
    – Joshua Grochow
    Commented Sep 16, 2013 at 19:14
  • 15
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Commented Sep 17, 2013 at 0:39
  • 4
    $\begingroup$ 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. $\endgroup$
    – Vijay D
    Commented Sep 18, 2013 at 22:04
  • 3
    $\begingroup$ 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. $\endgroup$
    – JRN
    Commented Sep 19, 2013 at 9:31
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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:

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – Artem Kaznatcheev ♦
    Commented Sep 20, 2013 at 20:29
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Commented Sep 20, 2013 at 21:59
  • $\begingroup$ addendum, another neat/interesting/recent ref Understanding computation by Stewart/O'Reilly, covers TMs, TM completeness etc using Ruby $\endgroup$
    – vzn
    Commented Sep 21, 2013 at 15:56
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Commented Sep 21, 2013 at 16:12
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Commented Sep 21, 2013 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.