Are there any expository books or articles on computability that are accessible to the general public on the order of Simon Singh's math popularizations (The Code Book)?

I'm looking for one with lots of pictures/diagrams (like Scientific American graphics) and low on mathematical notation.

It doesn't have to be a dedicated book. A book chapter, short article, or a (mostly self contained) series of blog posts is fine.

It should get across the concepts of Turing Machines and calculations, universal computation, and undecidability.


Not a direct answer, but still interesting: An exposition of the undecidability of the halting problem:

The Freeze App Does Not Exist

by Pål Grønås Drange and Jan Arne Telle from Bergen Univ., translated and rephrased by Thore Husfeldt, posted here.

      Freeze App

I also like the (now aging)

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

  • $\begingroup$ I like the phone app example. Almost makes it simple! $\endgroup$ – Mitch Jun 21 '16 at 12:42

Here are two books for "the intelligent layman" that explain those topics. They would be too difficult for many people but still explain the concepts in an interesting and basically non-technical way. As a bonus, these are both excellent, very famous books.

  • Gödel, Escher, Bach by Douglas R. Hofstadter. This book combines your ideas with those of art (Escher) and music (Bach) to analyze artificial intelligence.
  • The Emperor's New Mind by Roger Penrose. This book combines your ideas with those of quantum mechanics to argue against some claims about artificial intelligence.
  • 1
    $\begingroup$ Both of those are classic. Penrose's is controversial because of his non-standard understanding of Gödel's theorems. GEB is not controversial in content but, despite it being so accessible, most people find it over-the-top mind blowing. But I guess that's appropriate with undecidability. $\endgroup$ – Mitch Jun 21 '16 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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