Joshua Burns’s Reviews > Introduction to the Theory of Computation > Status Update

This textbook is top-tier, a joy to read

I had heard of Kolmogorov complexity but never realized it was definable in such an intuitive and simple way (264). Very neat.

The proof of Kleene's second recursion theorem for Turing machines was really cool, and the construction of general-purpose self-referential Turing machines was much more intuitively well-motivated than versions of this proof I've seen using binary code on register machines. (Chapter 6)