Here's a little writeup of how I could imagine mathematical proofs as a useful proof-of-work: https://pastebin.com/raw/ZAys0mYp

Note that it's more of a market for mathematical proofs, not a replacement for proof of work in a currency that needs a new block every 10 minutes.

Still, "miners" (theorem provers) get rewarded for their efforts with tokens.

My mathematician friends say such a genericized proof market should be possible using Model Theory.