Skip to content(if available)orjump to list(if available)

What can be computed? A practical guide to the theory of computation (2018) [pdf]

What can be computed? A practical guide to the theory of computation (2018) [pdf]

2 comments

·February 27, 2025
Visit

ccvannorman

What a wonderful text. Easy to read, concise, clear, interesting -- and above all, important.

I would add context for 2025 about the fundamental limits this places on what (modern) AI is in principal capable of. Perhaps some "non-computable" features would need to be hard-coded into AI, so that it could at least better approximate the types of incomputable problems we might ask it to do?

Also, a search of the text for "conscious" does not yield anything, which is probably a good thing. This text also reminds me of the questions like, "What does it mean to be conscious?" and, "How are human brains able to reason about (things like) incomputability, which in some sense, computers as we currently understand them could never do?" and, "What specifically beyond pure mathematics does a brain have or need in order to be conscious enough to reason about such things?"

ccvannorman

corollary: Numberphile (with Matt Parker of Stand Up Maths) - "All the Numbers". Most are incomputable, of course :)

[0] https://www.youtube.com/watch?v=5TkIe60y2GI&t=1s