<p>I know of many theoretical computer scientists whose first inspiration came from reading <a href="http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach" rel="noreferrer">Godel, Escher, Bach</a></p>

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

CC BY-SA 3.0
2013-09-18T21:26:55.677Z
Definitely true.
Giorgio Camerani
CC BY-SA 3.0
2013-09-19T03:17:09.493Z
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ε
CC BY-SA 3.0
2013-09-19T07:02:04.843Z
"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
CC BY-SA 3.0
2013-09-19T16:58:20.783Z
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
CC BY-SA 3.0
2013-09-20T05:56:53.687Z
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
CC BY-SA 3.0
2013-09-20T18:20:41.100Z
see also [learning Godel, Escher, Bach still valid today?](http://programmers.stackexchange.com/questions/10816/godel-escher-bach-still-valid-today) programmers.se
vzn
CC BY-SA 3.0
2013-09-20T20:22:59.403Z
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
CC BY-SA 3.0
2013-09-13T21:22:13.280Z
2013-09-20T20:15:58.740Z
2013-09-20T20:15:58.740Z
Aaron Roth
<p>After clarifying the (unclear for me) meaning of "popular science" (thanks Sasho :-) I propose:</p>

<p><strong>Title:</strong> Winning Ways for Your Mathematical Plays (4 volumes)</p>

<p><strong>Authors:</strong>  Elwyn R. Berlekamp, John H. Conway, Richard K. Guy</p>

<p><strong>Description:</strong> 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 href="http://citeseer.uark.edu:8080/citeseerx/showciting;jsessionid=589CCA846028E7D910E4660BF37854CE?cid=68471&amp;sort=recent">a source of inspiration</a> for many deeper results in <a href="http://en.wikipedia.org/wiki/Combinatorial_game_theory">combinatorial game theory</a>.</p>

<p><em>Addendum</em></p>

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

<p><strong>Resource:</strong>  The 'Mathematical Games and Recreations' column for Scientific American</p>

<p><strong>Author:</strong> Martin Gardner</p>

<p><strong>Description:</strong> 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.).</p>

CC BY-SA 3.0
2016-09-26T02:23:06.590Z
Upvoted just for Martin Gardner. I first learned about RSA from Mathematical Games, which has influenced my career since then.
nealmcb
CC BY-SA 3.0
2013-09-13T21:46:42.203Z
2013-09-14T12:14:03.513Z
2013-09-14T12:14:03.513Z
Marzio De Biasi
<p>Scott Aaronson's <a href="http://rads.stackoverflow.com/amzn/click/0521199565" rel="noreferrer">Quantum Computing Since Democritus</a>. 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. </p>

CC BY-SA 3.0
2013-09-17T01:29:20.110Z
2013-09-20T09:20:35.510Z
2013-09-20T09:20:35.510Z
user774025
<p>At the intersection of <a href="http://egtheory.wordpress.com/2013/09/09/cstheory-of-biology/">evolutionary biology and theoretical computer science</a> there are two recent books.</p>

<ul>
<li><p>Valiant's <em>"Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World"</em>, and</p></li>
<li><p>Chaitin's <em>"Proving Darwin: Making Biology Mathematical"</em>.</p></li>
</ul>

<p>Both books look at evolution through the <a href="http://egtheory.wordpress.com/2013/09/15/algorithmic-lens/">algorithmic lens</a>, with the first concentrating on how evolution, learning, and intelligence can be all expressed in the <a href="http://en.wikipedia.org/wiki/Probably_approximately_correct_learning">PAC-framework of Machine Learning</a>. The second book, looks at how to build a toy model of evolutionary innovation using algorithmic information theory. Although the books are <a href="http://egtheory.wordpress.com/2012/06/29/proving-darwin/">only loosely connected to biology</a>, 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.</p>

CC BY-SA 3.0
2013-10-03T23:14:18.933Z
fresh NYT review of [Valiant](http://www.nytimes.com/2013/10/01/science/probably-approximately-correct-explores-natures-algorithms.html)
vzn
CC BY-SA 3.0
2013-09-18T22:20:59.190Z
2013-09-18T22:20:59.190Z
Artem Kaznatcheev
<p>I first got interested in TCS after reading Scott Aaronson's writings; one of the earlier ones was <a href="http://www.scottaaronson.com/writings/bignumbers.html">Who Can Name the Bigger Number?</a>, which does have a pop-science feel to it</p>

<p>Another very good one I read later is <a href="http://www.scottaaronson.com/papers/philos.pdf">Why Philosophers Should Care About Computational Complexity</a>; 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.</p>

CC BY-SA 3.0
2013-09-19T05:34:33.677Z
2013-09-19T05:34:33.677Z
zodiac
<p>IMHO, I would recommend these "popular" books:</p>

<ol>
<li>Any book by <a href="https://en.wikipedia.org/wiki/James_Gleick" rel="nofollow">James Gleick</a> - <a href="https://en.wikipedia.org/wiki/Chaos%3a_Making_a_New_Science" rel="nofollow">Chaos</a>, <a href="https://en.wikipedia.org/wiki/The_Information%3a_A_History,_a_Theory,_a_Flood" rel="nofollow">The Information</a></li>
<li><a href="https://en.wikipedia.org/wiki/Fire_in_the_Valley%3a_The_Making_of_The_Personal_Computer" rel="nofollow">Fire in the Valley</a>, for an account of early PC history</li>
<li>Books by <a href="https://en.wikipedia.org/wiki/Steven_Levy" rel="nofollow">Steven Levy</a>: Insanely Great, <a href="https://en.wikipedia.org/wiki/In_the_Plex" rel="nofollow">In the Plex</a>, <a href="https://en.wikipedia.org/wiki/Hackers%3a_Heroes_of_the_Computer_Revolution" rel="nofollow">Hackers</a>, etc.</li>
</ol>

<p>And the grand master, though somewhat dated:</p>

<p><a href="https://en.wikipedia.org/wiki/The_Soul_of_a_New_Machine" rel="nofollow">The Soul of a New Machine</a> by Tracy Kidder</p>

CC BY-SA 3.0
2013-09-20T18:10:21.103Z
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
CC BY-SA 3.0
2016-09-26T02:24:36.060Z
Yes - Gleick's ***The Information*** is excellent!
nealmcb
CC BY-SA 3.0
2013-09-19T15:35:00.850Z
2013-09-19T20:40:26.373Z
2013-09-19T20:40:26.373Z
efutch
<p>The obvious answer would be Lance Fortnow's book <a href="http://press.princeton.edu/titles/9937.html"><em>The Golden Ticket</em></a> 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.)</p>

CC BY-SA 3.0
2013-09-13T20:46:02.293Z
My understanding on "inspire" is that the books should predate the development of TCS.
Yixin Cao
CC BY-SA 3.0
2013-09-13T20:56:53.480Z
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
CC BY-SA 3.0
2013-09-13T18:22:31.737Z
2013-09-13T18:22:31.737Z
David Richerby
<p>I liked:</p>

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

<p>I also liked:</p>

<p><strong>Douglas Hofstadter: Metamagical Themas</strong>, 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.</p>

<p>As a proper CS popular book, many people seem to like:</p>

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

CC BY-SA 3.0
2013-09-19T08:11:12.843Z
2013-09-19T08:16:26.103Z
2013-09-19T08:16:26.103Z
László Kozma
<p>The book <a href="http://www.springer.com/computer/general+issues/book/978-3-540-85985-7" rel="nofollow">Algorithmic Adventures</a> by Hromkovič is a rare attempt to explain some really mainstream ideas of theoretical computer science to a wide audience.</p>

CC BY-SA 3.0
2013-09-20T10:43:11.267Z
2013-09-20T10:43:11.267Z
042
<p>I was inspired by Stephen Wolfram's <a href="http://wolframscience.com/" rel="nofollow">A New Kind of Science</a>.  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).</p>

<p><i>Edit</i>:  It has been pointed out in the comments below that the book is controversial.  I quote <a href="http://arxiv.org/abs/quant-ph/0206089" rel="nofollow">a review</a> by Scott Aaronson:</p>

<blockquote>
  <p>[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.</p>
</blockquote>

CC BY-SA 3.0
2013-09-15T13:55:23.740Z
Are you aware that Wolfram is a little bit "controversial" among computer scientists?
Marcos Villagra
CC BY-SA 3.0
2013-09-15T13:57:05.267Z
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
CC BY-SA 3.0
2013-09-15T16:21:07.907Z
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](http://meta.cstheory.stackexchange.com/).
vzn
CC BY-SA 3.0
2013-09-16T19:14:38.133Z
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
CC BY-SA 3.0
2013-09-17T00:20:01.893Z
@JoshuaGrochow, thanks for the link and the suggestion.
JRN
CC BY-SA 3.0
2013-09-17T00:39:50.553Z
_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ε
CC BY-SA 3.0
2013-09-18T22:04:06.213Z
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
CC BY-SA 3.0
2013-09-18T23:28:15.473Z
@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
CC BY-SA 3.0
2013-09-19T00:27:15.627Z
@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
CC BY-SA 3.0
2013-09-19T01:51:45.220Z
@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
CC BY-SA 3.0
2013-09-19T03:16:20.430Z
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ε
CC BY-SA 3.0
2013-09-19T09:31:20.510Z
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
CC BY-SA 3.0
2013-09-19T16:17:32.683Z
@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
CC BY-SA 3.0
2013-09-19T17:08:26.030Z
see also [recent economist profile, wolfram](http://www.economist.com/node/18750658). also wikipedia has good [overview](http://en.wikipedia.org/wiki/A_New_Kind_of_Science)
vzn
CC BY-SA 3.0
2013-09-20T00:17:46.227Z
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](http://joelreyesnoche.wordpress.com/2012/11/14/thue-morse-sequence/).  I also used to do circuit design (computer arithmetic) but now my interests are elsewhere.
JRN
CC BY-SA 3.0
2013-09-13T23:32:02.653Z
2013-09-17T00:19:07.687Z
2013-09-17T00:19:07.687Z
JRN
<p>I will suggest the following books.</p>
<ol>
<li><p><a href="https://www.amazon.in/Golden-Ticket-NP-Search-Impossible/dp/0691156492" rel="nofollow noreferrer">The Golden Ticket: P, NP, and the Search for the Impossible</a> 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.</p>
</li>
<li><p><a href="https://www.amazon.in/Nature-Computation-Cristopher-Moore/dp/0199233217" rel="nofollow noreferrer">The Nature of Computation</a> 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.</p>
</li>
<li><p><a href="https://rads.stackoverflow.com/amzn/click/com/0385730624" rel="nofollow noreferrer" rel="nofollow noreferrer">The Code Book: The Secrets Behind Codebreaking</a> 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.</p>
</li>
</ol>

CC BY-SA 4.0
2021-04-09T14:58:38.857Z
2021-04-09T14:58:38.857Z
akr_
<p>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:</p>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/0691158193" rel="nofollow">Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers</a> MacCormick</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/1591844924" rel="nofollow">Automate This: How Algorithms Came to Rule Our World</a> Steiner</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0156013916" rel="nofollow">The Advent of the Algorithm: The 300-Year Journey from an Idea to the Computer</a> Berlinski</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0262518805" rel="nofollow">Algorithms Unlocked</a> Cormen</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0465032710" rel="nofollow">Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World</a> Valiant</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0387982698" rel="nofollow">Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientist</a> Sasha/Lazere</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0393322297" rel="nofollow">Engines of Logic: Mathematicians and the Origin of the Computer</a> Davis</li>
</ul>

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

<ul>
<li>quantum computing
<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/0521199565" rel="nofollow">Quantum computing since Democritus</a> Aaronson</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0738201731" rel="nofollow">The Feynman Processor : Quantum Entanglement and the Computing Revolution</a> Milburn</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0684814811" rel="nofollow">MINDS, MACHINES, AND THE MULTIVERSE: THE QUEST FOR THE QUANTUM COMPUTER</a> Brown</li>
</ul></li>
<li>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.]</li>
<li>cryptography</li>
<li>bioinformatics</li>
<li>etc!</li>
</ul>

CC BY-SA 3.0
2013-09-20T20:29:31.393Z
[Aaronson's](http://cstheory.stackexchange.com/a/19032/1037) and [Valiant's](http://cstheory.stackexchange.com/a/19077/1037) 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](http://egtheory.wordpress.com/2013/06/09/toward-an-algorithmic-theory-of-biology/) that there is not that much overlap. Similar goes for HFT, although [there are some connections](http://cstheory.stackexchange.com/q/7951/1037).
Artem Kaznatcheev
CC BY-SA 3.0
2013-09-20T21:59:54.953Z
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](http://meta.cstheory.stackexchange.com/questions/947/is-theoretical-computer-science-too-narrow)). 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 [tag:bioinformatics]
vzn
CC BY-SA 3.0
2013-09-21T15:56:26.250Z
addendum, another neat/interesting/recent ref [Understanding computation](http://www.amazon.com/exec/obidos/ASIN/1449329276/) by Stewart/O'Reilly, covers TMs, TM completeness etc using Ruby
vzn
CC BY-SA 3.0
2013-09-21T16:12:48.410Z
see also [Think Complexity: Complexity Science and Computational Modeling](http://www.amazon.com/Think-Complexity-Computational-Modeling-ebook/dp/B007ECM460/) by Downey/O'Reilly publisher. covers CAs, [small world] graphs, fractals, etc. Python code. influenced by Wolframs NKS.
vzn
CC BY-SA 3.0
2013-09-21T16:30:38.317Z
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](http://pragprog.com/book/mcmath/good-math) by Mark C. Chu-Carroll
vzn
CC BY-SA 3.0
2013-10-02T02:26:50.283Z
also [Shortcut through time:the path to the quantum computer](http://www.amazon.com/Shortcut-Through-Time-Quantum-Computer/dp/0375726187) by Johnson
vzn
CC BY-SA 3.0
2013-10-12T21:52:33.317Z
also [In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation](http://www.amazon.com/Pursuit-Traveling-Salesman-Mathematics-Computation/dp/0691152705/) by Cook
vzn
CC BY-SA 3.0
2013-09-19T15:35:40.583Z
2013-09-19T15:42:44.050Z
2013-09-19T15:42:44.050Z
vzn
<p>There is a reputation, that in computer science, we do not have popular science books. Of course that's not really true! </p>

<p>(In the same spirit of list of <a href="https://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read">What Books Should Everyone Read?</a>, <a href="https://cstheory.stackexchange.com/questions/1168/what-papers-should-everyone-read">What papers should everyone read?</a>, <a href="https://cstheory.stackexchange.com/questions/1198/what-videos-should-everybody-watch">What videos should everybody watch?</a> and inspired from <a href="https://mathoverflow.net/questions/8609/favorite-popular-math-book">Favorite popular math book</a>)</p>

<p>What are the popular science books or resources that inspire CS Theory?</p>

<p>Please have some description about why the book would be nice.</p>

CC BY-SA 3.0
2013-09-13T19:40:31.200Z
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
CC BY-SA 3.0
2013-09-13T20:27:13.723Z
@MarzioDeBiasi http://en.wikipedia.org/wiki/Popular_science
Sasho Nikolov
CC BY-SA 3.0
2013-09-14T00:00:28.280Z
I think the question should be community wiki.
Boris Bukh
CC BY-SA 3.0
2013-09-14T02:15:36.577Z
not phrased so specifically however a reasonable angle is "_nontechnical_ books that inspire people to further learn/study TCS"
vzn
CC BY-SA 3.0
2013-09-14T02:37:12.497Z
I think _non-technical_, _easily accessible_ are the good keywords here.
Subhayan
CC BY-SA 3.0
2013-09-17T17:35:16.990Z
[Brian Hayes](http://en.wikipedia.org/wiki/Brian_Hayes_(scientist)) 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](http://www.americanscientist.org/authors/detail/brian-hayes), but the TCS-focused elements not compiled into a book (yet?). blogging at ["bit-player"](http://bit-player.org/).
vzn
<big-list><books>
What are the popular science books that inspire TCS?
Subhayan
# What are the popular science books that inspire TCS?

(Asked by: username_0 on 2013-09-13)

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?](https://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read), [What papers should everyone read?](https://cstheory.stackexchange.com/questions/1168/what-papers-should-everyone-read), [What videos should everybody watch?](https://cstheory.stackexchange.com/questions/1198/what-videos-should-everybody-watch) and inspired from [Favorite popular math book](https://mathoverflow.net/questions/8609/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.

**Tags:** big-list, books

> **Comments:**
> **username_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).  
> **username_2**: @MarzioDeBiasi http://en.wikipedia.org/wiki/Popular_science  
> **username_3**: I think the question should be community wiki.  
> **username_4**: not phrased so specifically however a reasonable angle is "_nontechnical_ books that inspire people to further learn/study TCS"  
> **username_0**: I think _non-technical_, _easily accessible_ are the good keywords here.  
> **username_4**: [Brian Hayes](http://en.wikipedia.org/wiki/Brian_Hayes_(scientist)) 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](http://www.americanscientist.org/authors/detail/brian-hayes), but the TCS-focused elements not compiled into a book (yet?). blogging at ["bit-player"](http://bit-player.org/).  

---

## 12 answers

### Answer by username_5 on 2013-09-13. Score: 24

I know of many theoretical computer scientists whose first inspiration came from reading [Godel, Escher, Bach](http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach)

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

> **Comments:**
> **username_6**: Definitely true.  
> **username_7**: 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.  
> **username_8**: "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  
> **username_9**: 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.  
> **username_8**: 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.  
> **username_4**: see also [learning Godel, Escher, Bach still valid today?](http://programmers.stackexchange.com/questions/10816/godel-escher-bach-still-valid-today) programmers.se  
> **username_10**: 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.  

---

### Answer by username_1 on 2013-09-13. Score: 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](http://citeseer.uark.edu:8080/citeseerx/showciting;jsessionid=589CCA846028E7D910E4660BF37854CE?cid=68471&sort=recent) for many deeper results in [combinatorial game theory](http://en.wikipedia.org/wiki/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.).

> **Comments:**
> **username_11**: Upvoted just for Martin Gardner. I first learned about RSA from Mathematical Games, which has influenced my career since then.  

---

### Answer by username_12 on 2013-09-17. Score: 14

Scott Aaronson's [Quantum Computing Since Democritus](http://rads.stackoverflow.com/amzn/click/0521199565). 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.


---

### Answer by username_10 on 2013-09-18. Score: 7

At the intersection of [evolutionary biology and theoretical computer science](http://egtheory.wordpress.com/2013/09/09/cstheory-of-biology/) 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](http://egtheory.wordpress.com/2013/09/15/algorithmic-lens/), with the first concentrating on how evolution, learning, and intelligence can be all expressed in the [PAC-framework of Machine Learning](http://en.wikipedia.org/wiki/Probably_approximately_correct_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](http://egtheory.wordpress.com/2012/06/29/proving-darwin/), 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.

> **Comments:**
> **username_4**: fresh NYT review of [Valiant](http://www.nytimes.com/2013/10/01/science/probably-approximately-correct-explores-natures-algorithms.html)  

---

### Answer by username_13 on 2013-09-19. Score: 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?](http://www.scottaaronson.com/writings/bignumbers.html), which does have a pop-science feel to it

Another very good one I read later is [Why Philosophers Should Care About Computational Complexity](http://www.scottaaronson.com/papers/philos.pdf); 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.


---

### Answer by username_14 on 2013-09-19. Score: 6

IMHO, I would recommend these "popular" books:

1. Any book by [James Gleick](https://en.wikipedia.org/wiki/James_Gleick) - [Chaos](https://en.wikipedia.org/wiki/Chaos%3a_Making_a_New_Science), [The Information](https://en.wikipedia.org/wiki/The_Information%3a_A_History,_a_Theory,_a_Flood)
2. [Fire in the Valley](https://en.wikipedia.org/wiki/Fire_in_the_Valley%3a_The_Making_of_The_Personal_Computer), for an account of early PC history
3. Books by [Steven Levy](https://en.wikipedia.org/wiki/Steven_Levy): Insanely Great, [In the Plex](https://en.wikipedia.org/wiki/In_the_Plex), [Hackers](https://en.wikipedia.org/wiki/Hackers%3a_Heroes_of_the_Computer_Revolution), etc.

And the grand master, though somewhat dated:

[The Soul of a New Machine](https://en.wikipedia.org/wiki/The_Soul_of_a_New_Machine) by Tracy Kidder

> **Comments:**
> **username_4**: 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.  
> **username_11**: Yes - Gleick's ***The Information*** is excellent!  

---

### Answer by username_15 on 2013-09-13. Score: 5

The obvious answer would be Lance Fortnow's book [*The Golden Ticket*](http://press.princeton.edu/titles/9937.html) 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.)

> **Comments:**
> **username_16**: My understanding on "inspire" is that the books should predate the development of TCS.  
> **username_15**: 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?  

---

### Answer by username_17 on 2013-09-19. Score: 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.


---

### Answer by username_18 on 2013-09-20. Score: 2

The book [Algorithmic Adventures](http://www.springer.com/computer/general+issues/book/978-3-540-85985-7) by Hromkovič is a rare attempt to explain some really mainstream ideas of theoretical computer science to a wide audience.


---

### Answer by username_19 on 2013-09-13. Score: 2

I was inspired by Stephen Wolfram's [A New Kind of Science](http://wolframscience.com/). 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](http://arxiv.org/abs/quant-ph/0206089) 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.

> **Comments:**
> **username_20**: Are you aware that Wolfram is a little bit "controversial" among computer scientists?  
> **username_19**: 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?  
> **username_4**: 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](http://meta.cstheory.stackexchange.com/).  
> **username_21**: 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.)  
> **username_19**: @JoshuaGrochow, thanks for the link and the suggestion.  
> **username_7**: _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_.  
> **username_8**: 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.  
> **username_19**: @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.  
> **username_8**: @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?  
> **username_20**: @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.  
> **username_7**: 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.  
> **username_19**: 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.  
> **username_8**: @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.  
> **username_4**: see also [recent economist profile, wolfram](http://www.economist.com/node/18750658). also wikipedia has good [overview](http://en.wikipedia.org/wiki/A_New_Kind_of_Science)  
> **username_19**: 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](http://joelreyesnoche.wordpress.com/2012/11/14/thue-morse-sequence/).  I also used to do circuit design (computer arithmetic) but now my interests are elsewhere.  

---

### Answer by username_22 on 2021-04-09. Score: 1

I will suggest the following books.

1. [The Golden Ticket: P, NP, and the Search for the Impossible](https://www.amazon.in/Golden-Ticket-NP-Search-Impossible/dp/0691156492) 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](https://www.amazon.in/Nature-Computation-Cristopher-Moore/dp/0199233217) 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](https://rads.stackoverflow.com/amzn/click/com/0385730624) 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.


---

### Answer by username_4 on 2013-09-19. Score: 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:

* [Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers](http://rads.stackoverflow.com/amzn/click/0691158193) MacCormick
* [Automate This: How Algorithms Came to Rule Our World](http://rads.stackoverflow.com/amzn/click/1591844924) Steiner
* [The Advent of the Algorithm: The 300-Year Journey from an Idea to the Computer](http://rads.stackoverflow.com/amzn/click/0156013916) Berlinski
* [Algorithms Unlocked](http://rads.stackoverflow.com/amzn/click/0262518805) Cormen
* [Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World](http://rads.stackoverflow.com/amzn/click/0465032710) Valiant
* [Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientist](http://rads.stackoverflow.com/amzn/click/0387982698) Sasha/Lazere
* [Engines of Logic: Mathematicians and the Origin of the Computer](http://rads.stackoverflow.com/amzn/click/0393322297) Davis

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

* quantum computing
  + [Quantum computing since Democritus](http://rads.stackoverflow.com/amzn/click/0521199565) Aaronson
  + [The Feynman Processor : Quantum Entanglement and the Computing Revolution](http://rads.stackoverflow.com/amzn/click/0738201731) Milburn
  + [MINDS, MACHINES, AND THE MULTIVERSE: THE QUEST FOR THE QUANTUM COMPUTER](http://rads.stackoverflow.com/amzn/click/0684814811) Brown
* 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!

> **Comments:**
> **username_10**: [Aaronson's](http://cstheory.stackexchange.com/a/19032/1037) and [Valiant's](http://cstheory.stackexchange.com/a/19077/1037) 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](http://egtheory.wordpress.com/2013/06/09/toward-an-algorithmic-theory-of-biology/) that there is not that much overlap. Similar goes for HFT, although [there are some connections](http://cstheory.stackexchange.com/q/7951/1037).  
> **username_4**: 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](http://meta.cstheory.stackexchange.com/questions/947/is-theoretical-computer-science-too-narrow)). 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 [tag:bioinformatics]  
> **username_4**: addendum, another neat/interesting/recent ref [Understanding computation](http://www.amazon.com/exec/obidos/ASIN/1449329276/) by Stewart/O'Reilly, covers TMs, TM completeness etc using Ruby  
> **username_4**: see also [Think Complexity: Complexity Science and Computational Modeling](http://www.amazon.com/Think-Complexity-Computational-Modeling-ebook/dp/B007ECM460/) by Downey/O'Reilly publisher. covers CAs, [small world] graphs, fractals, etc. Python code. influenced by Wolframs NKS.  
> **username_4**: 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](http://pragprog.com/book/mcmath/good-math) by Mark C. Chu-Carroll  
> **username_4**: also [Shortcut through time:the path to the quantum computer](http://www.amazon.com/Shortcut-Through-Time-Quantum-Computer/dp/0375726187) by Johnson  
> **username_4**: also [In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation](http://www.amazon.com/Pursuit-Traveling-Salesman-Mathematics-Computation/dp/0691152705/) by Cook  

---

