Impossible Programs

At Scottish Ruby Conference 2013 and GoGaRuCo 2013 I gave a talk called Impossible Programs, adapted from chapter 8 of Understanding Computation. It’s a talk about programs that are impossible to write in Ruby — it covers computational universality, undecidability, the halting problem and Rice’s theorem, explained in plain English and illustrated with Ruby code. The slides are available, and here’s the video:

To make the talk fit into a 45-minute slot I had to cut several sections out. One of those sections explained why it’s always okay to talk about programs which read their own source code: there’s a mathematical result called Kleene’s recursion theorem which guarantees that any program can be extended to compute its own source. For fun I tried to cram this leftover material into a five-minute lightning talk; here are the slides, and here’s the video (my talk starts at 13:40):

If you find this sort of thing interesting, please check out the sample chapter and code — there’s lots more in the book.