A "proof of computation" system is another use case that occurs to me - it has similar characteristics.
Hmm ... but with limited applications, at least as far as I understand the approach:
https://en.wikipedia.org/wiki/Verifiable_computing.
It is like hashing or SAT. That is, computing the function is easy but reversing it should be hard.
For instance, I doubt, that computing graphics for games or movies is one of such problems. You need problems for which people are willing to pay lots of money. A big decentralized SAT-solver is too abstract for virtually everyone and, thus, won't work as killer application.
And, imho, computing the same stuff several times for comparison is ugly (SETI@home), or at least inelegant.
However, these use cases are relatively simple, and they would very likely not need a Turing complete smart contract language - these functions can be part of the hard-coded "standard feature set" of a cryptocurrency protocol and/or client software.
Exact! In the worst case, the protocol is extended (slowly and incrementally).