I remember that the book "Feynman's Lectures on Computation" has some excellent descriptions of basic computing models (FSMs, Turing machines, ...) as well as i

I remember that the book "Feynman's Lectures on Computation" has some excellent descriptions of basic computing models (FSMs, Turing machines, ...) as well as interesting exercises in constructing "programs" using those models. It may not be as practical as he/you are looking for, but I think it might be a great choice because it does an amazing job explaining the basic theory of computation and the "programs" called for in the exercises can be easily run by hand, on paper. It might be a good place to start, at the very least. But it will only appeal to a certain sort of person.