If you want the proof of work to involve a fixed algorithm, it seems doable.  It is not my central focus, but I describe a way of doing this in the white paper that link of Stephen Gornick's is discussing, and another participant on this forum has stated that he's building a business around a framework for such blockchains.  Based on my current understanding, the main problem is ensuring simultaneous consistency and efficiency of calculations across platforms.