5 ms·
I apologise ahead for posting something in response to this which is technically off topic, and unfortunately also mentions blockchains. The comment by 'yaseer'
by jiggawatts 5y ago
I apologise ahead for posting something in response to this which is technically off topic, and unfortunately also mentions blockchains. The comment by 'yaseer' reminded me of a vaguely related idea, so I figured some people reading this might be interested...
What if instead of a chain-of-proofs-of work, there would be a chain-of-proofs?
And, what if instead of a chain, it was a directed-acyclic-graph-of -proofs?
(From now on I will use the term blockgraph instead of blockchain to disambiguate.)
Lastly: instead of a giant Ponzi scheme of useless deflationary pretend money, what if the blockgraph was simply backed by real dollars used to reward useful proofs?
That last bit is the most important: What's a useful proof? Why would anyone pay money for such a thing? Why would anyone care about a not-a-blockchain that won't make anyone super rich?
I like to imagine a "superoptimising compiler" that has a $1K/annum license. That's peanuts to a FAANG or even a medium-to-large org with a development team. This money would go "into the blockgraph"[1], compensating the authors of the "most useful proofs of more optimal code sequences".
Obviously a lot of effort would have to go into designing the blockgraph to avoid it being gamed or abused, because it is a lot more complex than comparatively trivial proof-of-work linear chains like Bitcoin.
The idea is that each proof published to the blockgraph would be identified by its hash, and would build upon existing proofs in the chain by referencing their hash codes in turn. So each proof would be a series of terms, most of which would be cross-references, as well as some novel steps that are difficult to generate but trivial to verify.
To disincentivise users spamming true but useless proofs such as "1+1=2" and "2+2=4", the system would have to penalise proofs based on the data volume of their novel component plus some smaller penalty of the total number of references, plus an even smaller penalty for indirect (transitive) references.
Existing proofs that are referenced get a "cut" of the real money income granted to proofs that reference them. This makes single-use proofs worthless to publish, and widely usable proofs potentially hugely lucrative.
Publishing shortcuts in the proof graph are rewarded, because then other proofs can be made shorter in turn, making them more profitable than longer proofs.
Etc...
In general, the design goal of the whole system is to have a strong incentive to publish short, efficient proofs that reuse the existing blockgraph as much as possible and can in turn be reused by as many other users as possible. This makes the data volume small, and proofs efficient to verify.
The people putting up real money can get their "problems solved" automatically via a huge marketplace of various proofs systems[2] interacting and enhancing each other.
Want a short bit of code optimised to death? Put the "problem" up on the blockgraph for $5 and some system will try to automatically find the optimal sequence of assembly instructions that provably results in the same outcome but in less CPU time.
A compiler could even do this submission for you automatically. Feed in $1K of "optimisation coins" and have it put up $50 every time there's a major release planned.
Want to optimise factory production scheduling with fiendishly complex constraints? Put up $10K on the blockgraph! If it gets solved, it's solved. If not... you don't lose your money.
Etc...
[1] The obvious way to do this would be to link the blockgraph to an existing chain like Bitcoin or Ethereum, but it could also be simply a private company that pays out the rewards to ordinary bank accounts based on the current blockgraph status.
[2] Don't assume computers! This isn't about rooms full of GPUs burning coal to generate useless hash codes. A flesh and blood human could meaningfully and profitably contribute to the blockgraph. A particularly clever shortcut through the proof space could be worth millions, but would never be found by automated systems.
- wrnr 5y agoI don't know about theorem provers but computational algebra systems work a bit like a blockhain. At least they both use a merkle tree to store their graph/tree/list, but somewhere in your description there is a reformulation of the halting problem. It is impossible to know what rule is going to be useful next, CAS systems will often just use the length of the expression to decide this order. Like knuth said once, maybe P=NP but P is just impractically big.
- sva_ 5y agoI actually thought about this for a while, but I ended up not thinking that it'd work, because (among some other things which you also touched on) > To disincentivise users spamming true but useless proofs such as "1+1=2" and "2+2=4", the system would have to penalise proofs based on the data volume of their novel component I believe that this stated goal of defining a metric that decides which theorems are "interesting" is a lot more difficult than finding proofs for theorems. I think at some point proving things will to a large part be automatic, and mathematicians will mostly concern themselves with finding interesting theorems, definitions, and axioms, rather than wasting time on proving-labor. But what do I know.
- jiggawatts 5y ago"Interesting" cannot be defined in an automatically verifiable way. "Useful & short" however can be. Useful proofs are ones that solve the problems that are placed on the chain with real money rewards. The length/size of the proof is trivially verifiable. Useful AND short is the combination that's required. "Useful" alone would result in duplicate spam. Merely "short" would result in bulk generation of useless proofs. "Useful and short" means that the core of the graph would be optimised much like ants looking for food. Shorter AND useful paths to many goals are automatically rewarded. Longer paths can exist, but as they get more used, the incentive to try and optimise them rises dramatically to the point where even humans might want to contribute clever shortcuts manually.
- sva_ 5y agoYeah man, but I'm not talking about the proof. I'm talking about the statement that has to be proved.