There is a problem in programming that has all the necessary properties of a problem for PoW. Namely Conway's Game of Life: https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

The idea is that given a set incoming parameters (a distribution of "cells" on a 2D-board) you can quite easily calculate the next step. But it is very hard to get the previous step and there are multiple solutions to the problem (many initial distributions can lead to a certain final distribution). There is no certain algorithm to reverse a step (this statement can be proven).

One does not have to use the classical game of life as is. There are numerous variations of it. In more than two dimensions, in hexagonal grid, multicolored etc.

The sequence might be as follows (I am using classical Conway's Game of Life as an example):

1. We start with an empty plane.

2. A miner picks a block and projects it on the plane in some predetermined way (like a long string of alternating 1/0).

3. Now he races with other miners to solve the problem: find any distribution that would include the block and would lead to an empty plane on the next step.

4. Whoever succeeds adds his distribution as a new default state.

5. Next miner adds the next block and he is solving a problem of finding a distribution that would include his block and would lead to the default distribution. It is easier to imagine if you add a rule that the miner's part of distribution has to be above the line of bytes that represents a block. In that case every next block will be added below whatever has evolved above.

6. Repeat with every block.

If one wants to check the chain on the block N he just plays the current distribution forward N steps and he will have to get to an empty plane.

You can change difficulty by using extra restrictions, like "The solution has to use less than X new cells" or "The solution has to be less then Y rows high" or any other.

The advantages of this PoW problem:

1. You can visualize the process. As long as you stay in 2 or 3 dimensions.

2. There is a potential for evolution of some very complex structures. One can build Turing machines in 2d classical Game of Life. So there is no theoretical obstacles for full-scale life forms (things that reproduce and evolve) or even self-aware life forms in this perfect mathematical world. It just has to be big enough and will require a lot of computational power.

3. Mass scale computing of this kind of problems has real life applications. Lets say we make all the miners play some kind of a 3d game of life. Then we watch how it unravels until we see a part that behaves in a particular way (for example it pulses with a given period) than we can replicate this solution in a hardware where each little part is following the rules of the game. Increasing the density of small-parts that follow the rules of our game like we did with transistors we can create a lot of neat stuff.

4. Anything is better then mindless hash-calculations.

Comments are welcome.