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