Take a look at: Understanding Computation: From Simple Machines to Impossible Programs by Tom Stuart.

It's pretty much "computation theory for the everyday programmer". It uses Ruby to implement things like Turing Machines and the lambda calculus. Extremely accessible, and a lot of fun.