A truly decentralised consensus mechanism is one where humans perform the PoW. The trouble is, finding a problem that only a human can solve that is also easily verifiable by a machine is unsolved.
The person who solves this problem will be very rich indeed.
Rich like satoshi? We in the open source world aren't driven by riches.
You posed a great definition of the problem and with such I got inspired with a solution.
I think the answer lies in any algorithmicly unsolved math problem like "travelling salesman" or any other problem that relies on heuristics. Simple.
https://www.education.com/reference/article/problem-solving-strategies-algorithms/NP-Complete problems would be the perfect solution you are asking for.
https://en.m.wikipedia.org/wiki/NP-completenessTravelling salesman may be ideal because humans are good at it. Bees can also solve it.
"The TSP (traveling salesman problem) in particular the Euclidean variant of the problem, has attracted the attention of researchers in cognitive psychology. It has been observed that humans are able to produce near-optimal solutions quickly, in a close-to-linear fashion, with performance that ranges from 1% less efficient for graphs with 10-20 nodes, and 11% more efficient for graphs with 120 nodes.[47][48] The apparent ease with which humans accurately generate near-optimal solutions to the problem has led researchers to hypothesize that humans use one or more heuristics, with the two most popular theories arguably being the convex-hull hypothesis and the crossing-avoidance heuristic.[49][50][51] However, additional evidence suggests that human performance is quite varied, and individual differences as well as graph geometry appear to impact performance in the task.[52][53][54] Nevertheless, results suggest that computer performance on the TSP may be improved by understanding and emulating the methods used by humans for these problems, and have also led to new insights into the mechanisms of human thought.[55] The first issue of the Journal of Problem Solving was devoted to the topic of human performance on TSP,[56] and a 2011 review listed dozens of papers on the subject.[55]"