The design is very purposefully limited to keep the validation computation so cheap that it is effectively free, and no amount of fee paying can convince miners to allow more computation since the limits are a property of the system enforced by all nodes just as the supply of coin is limited.

I think it's a less useful mental model to think of what Bitcoin is doing as execution. What a Bitcoin script is really is a witness of an execution that the signer performed— proof that he executed it faithfully— rather than the computation itself. It's just a product of engineering that the simplest (to implement) way to verify execution is to perform it again, but its not intrinsic.