Sure, but are they provable in polynomial time?
Proof generation is much more expensive than just running through the original computation through standard means.
> However with some cool zero-knowledge crypto magic, you don't even have to reveal the Merkle inclusion proof, nor even the key itself.
I hate that the exact way that ZK systems work is always omitted from any discussion of the subject. It is very complicated, which explains why no one like to (or is even able to) get into the specifics, but somehow this also leads to handwavy assertion that all we need to do to avoid all that expensive and duplicative computation is to sprinkle in some zero-knowledge proofs.
Due to performance limitations, for all intents and purposes ZK tech is impractical to the point of being infeasible for truly decentralized blockchains with turing-complete smart contract capabilities. It works for more specialized purposes, but it is not a currently solution to the "duplicative computation" problem.