LESSWRONG
LW

569
An Opinionated Guide to Computability and Complexity

An Opinionated Guide to Computability and Complexity

Jul 24, 2023 by Noosphere89

I'm going to write a lot about computability and complexity, but the focus of the sequence is what machines are out there to compute different objects, to rank them, and in particular to focus on what computability and complexity finally to explain what problems we can solve in practice.

Along the way, I'll be making commentary and interacting with the subject, and I definitely will be making a post about a paper by Aaronson on what complexity theory adds to philosophy, as well as critique it and make it interesting and interactive.

10An Opinionated Guide to Computability and Complexity (Post #0)
Noosphere89
2y
10
6Why you can't treat decidability and complexity as a constant (Post #1)
Noosphere89
2y
13
-5Hilbert's Triumph, Church and Turing's failure, and what it means (Post #2)
Noosphere89
2y
16