The short answer is, it's really hard to make that work with the maths.

The way that bitcoin, and most block chains, work is that almost all of the work has to be wasted, because you want someone to find "the best" answer for a very hard problem. Also, some part of the answer to that problem has to involve the transactions.

You could do something like: Find the best match to (say) a polynomial of the SETI data of today, if I randomly corrupt it with the hash of some bitcoin transactions, except that isn't useful if the corruption destroys the problem you really care about, and it isn't useful (for bitcoin) if the transactions don't significantly effect the problem.

Decoupling doesn't seem like the hard problem to me.. I.e. if you somehow have a separate SETI chain of verified claims about the hashes of sectors then it is easy to change the satisfiability problem to one where you need to buy your solution to the transaction chain hash as an inclusion a reference to a portion of a cycle in the other chain (which determines the payout of new coins, leaving you transaction fees.)

The problem is you need it to be expensive to change a block, so the seti work needs to depend on the transactions it signs, else it is too cheap to produce modified block chains.

Using the transactions to make a block hard to change is the best option for a self contained chain with no other work, but a chain of work/work verification seems like it can be decoupled from monetary transaction chains or anything other than the transactions in parties proving and taking credit for pieces in the real work.

The difficulties should be pretty normal. Past blocks need to influence new cycles such that the current chain doesn't speed up work for building a new alternate, etc.

If a chain needed to pull a satisfactory reference from the Bitcoin chain and reward the transaction parties its new coin that wouldn't change Bitcoin's status which is either backed by it's own Bitcoin transactions or not.

Therefore, I see no need for tight coupling between real work chains and coin chains to start making rewarding real work a social requirement/pressure for any new coinage.

We aren't moving towards useful proof-of-work because the goal of Bitcoin is to agree on one, single chain of events. By making the calculations useful, there would be greater incentive to have competing chains, which is avoided by choosing something otherwise useless, such that an adversary has to waste work in order to promote a different main chain.