What if the proof of work could include a random set of AI problems? A quick hash of the transactions would randomize a problem set generator which creates a bunch of random machine learning, pattern matching, and similar problems. The node which releases the most efficient script for solving all of the problems in that random set wins the coins for that block.
Difficulty would increase by creating ever-harder AI problems rather than ever-harder hash targets.
Solution propagation would be interesting, since you're looking for the most efficient solution rather than a solution better than a certain threshold, and testing a proposed solution would take a lot longer than testing a hash. I think maybe each node would have to broadcast its best solution generated or received, and after 10 minutes, the best solution would be frozen and work would start on the next block. Everyone who helped propagate the winning solution would also get a small reward.
Once a solution was accepted, the network would test a random selection of previously-accepted scripts and give an additional reward to the one which happened to do well on this problem set, rewarding flexibility.
Since every script would be public, there would be fierce competition to build on previous best solutions and rapidly evolve solutions to very difficult AI problems. "Efficiency" could be judged in such a way that allows multiple copies of a candidate script to run and interact with copies of itself. Whoever does the best job of creating a basic unit of intelligence would get the rewards - a race to "build a better neuron".
This is probably unworkable in some way that is not clear to me at the moment, but it sure would be cool if it worked. On the other hand, maybe creating something like this is a bad idea even if it does work
