Comment by gwern

> They already do. Incompleteness Theorem ("some statements can neither be proved nor disproved", e.g., The Halting Problem which is incomplete) is one of the most significant achievements in logic.

Aaronson covers this, pointing out that those results are both in computability theory, not complexity.