Popularizing TOC

It is hard to overestimate the impact of Popular Science books such as “A Brief History of Time” and “Chaos: Making a New Science” on Scientific Research. The indirect impact of popularizing Science and Scientific Education often surpass the direct contribution that most scientists can hope to achieve in their life time. For this reason, many of the greatest scientists (including in our field) choose to invest considerable time in this blessed endeavor. I personally believe that the Theory of Computing deserves more popularization than it gets (and I hope to someday contribute my share). Nevertheless, this post is meant as a tribute to our colleagues who already made wonderful such contributions. I will continuously edit this post with TOC popular books and educational resources (based on my own knowledge and suggestions in the comments).

Popular TOC books:

Scott Aaronson, Quantum Computing since Democritus

Martin Davis, Engines of Logic: Mathematicians and the Origin of the Computer

A. K. Dewdney, The New Turing Omnibus: Sixty-Six Excursions in Computer Science

David Harel, Computers Ltd.: What They Really Can’t Do

David Harel with Yishai Feldman, Algorithmics: The Spirit of Computing

Douglas Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid

Lance Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible

Cristopher Moore and Stephan Mertens, The Nature of Computation

Dennis Shasha and Cathy Lazere, Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists

Leslie Valiant, Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World

Leslie Valiant, Circuits of the Mind

Noson S. Yanofsky, The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us

Hector Zenil, Randomness Through Computation: Some Answers, More Questions


Apostolos Doxiadis and Christos Papadimitriou, Logicomix: An epic search for truth

Christos H. Papadimitriou, Turing (A Novel about Computation)

Other Resources:

CS Unplugged (including a book)


12 thoughts on “Popularizing TOC

  1. I completely agree: popularizing TOC is an important and worthy goal. Speaking for myself, I remember reading David Harel’s “Algorithmica” as the moment when I started falling in love with TOC.

  2. a very worthwhile endeavor but youd be very surprised how many excellent books there are now, its somewhat exploded in recent years with the rise of CS/ internet, “algorithmic age” and “algorithmic lens” etc. note that amazon book lists might be a nice way to organize this. and it would even be cool to set up a voting system for entries.
    one of my recent favorites not mentioned yet is Fortnow on P vs NP
    see also what are the pop sci books that inspire CS

      1. I’m a bit hesitant to add wide-audience talks (as valuable as they are) in the body of the post, just because there are so many of those. But the comment section could be a great place to add more talks that people liked.

  3. A.K Dewdney’s “The (New) Turing Omnibus” is nice introduction to interesting TCS problems of the sort that is great for the motivated high-school student.

  4. James Gleick’s “The Information: A History, a Theory, a Flood”

    Stephen Levy’s “Crypto: How the Code Rebels Beat the Government—Saving Privacy in the Digital Age”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s