Joshua Burns’s Reviews > Introduction to the Theory of Computation > Status Update
Joshua Burns
is on page 265 of 431
I had heard of Kolmogorov complexity but never realized it was definable in such an intuitive and simple way (264). Very neat.
— May 14, 2025 05:58PM
Like flag
Joshua’s Previous Updates
Joshua Burns
is on page 252 of 431
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)
— May 14, 2025 05:16PM
