Skip to content

Popularizing TOC

July 1, 2015

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 Comments leave one →
  1. Guy Rothblum permalink
    July 1, 2015 6:44 pm

    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. July 1, 2015 7:58 pm

    L. Valiant’s “Probably Approximately Correct” is very nice.

  3. July 2, 2015 12:37 am

    Hofstadter, *Gôdel, Escher, Bach,* seems like a natural inclusion.

  4. July 2, 2015 1:42 am

    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

  5. July 2, 2015 8:57 am

    typo: Less Valiant -> Leslie Valiant

  6. July 2, 2015 11:22 am

    Christos Papadimitriou has “Turing (a Novel about Computation)” and “Logicomix”.

  7. July 4, 2015 7:01 pm

    Moore and Mertens: The Nature of Computation

    • July 5, 2015 5:29 am

      Vardi’s videotaped lecture: And Logic Begat Computer Science: When Giants Roamed the Earth (I am not aware of a written version)

      • July 7, 2015 5:22 pm

        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.

  8. Paul Beame permalink
    July 7, 2015 2:20 am

    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.

  9. July 11, 2015 7:30 pm

    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: Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: