# 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

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