Standard complexity theory focuses on answering questions when our substrate behaves like a Turing machine with multiple tapes.

Consider it like this, if the answer is in our system's axioms, we don't have to do anything. In a trivial sense that means we're just given the answer table, but it's also true if our substrate matches the model of computation its simulating. IE for an SLD-Resolution machine, running an SLD-Resolution object language, unification is worst case O(1). This is a degenerate case of course, but it's an example of something that's not realizable on a Turing machine's semantics where the worst case is in... EXPTIME? It's not great.

The more we treat our substrate like building blocks, and less like a holistic oracle, that changes our complexity landscape. Complexity theory was never about studying that whole landscape.

You might want to say CT is pragmatic and focused on realizable machines. There are two problems with that:

1. There's nothing special with the baseline used for complexity theory other than its familiarity. Reality is our ultimate substrate. The universe is not Turing tape. There is absolutely no serious basis upon which an argument against substrates can be made, especially with how little we know and understand about the universe.

2. Complexity theory isn't so pragmatic to only study the finitely bounded, which also changes everything. There seems a very tight upper bound on information in the universe. Even studying up to it as a limit is decidedly not pragmatic in the slightest. This is perfectly fine of course, the problem only enters in when we want to be "pragmatic" on some things, but not others.

I also want to clarify: There are higher orders of complexity theory that have generalized a lot of its concepts, even into hypercomputation which is cool, but then there's another problem I didn't mention. Complexity theory still isn't about what he said. It quantifies that distance between prove and verify, but it doesn't study the set of all those distances and how they arise. It just quantifies them one at a time and has only a limited number of things to say beyond that. What he described is simply mathematical logic.

> Standard complexity theory focuses on answering questions when our substrate behaves like a Turing machine with multiple tapes.

This is not true. Complexity theory very much looks at complexity under different models (alphabet size, oracles, circuits). It's just that often (e.g. in the case of alphabets), there is a reduction of known complexity between two models.

> It quantifies that distance between prove and verify, but it doesn't study the set of all those distances and how they arise.

This is also not true (https://en.wikipedia.org/wiki/Proof_complexity).

Isn't complexity theory usual based on a random-access model, not any kind of Turing machine?