一个叫Yanhong A. Liu多伦多大学计算机教授给tauchain老大发了以下邮件
A.是Annie的缩写。
另外，这个Yanhong A. Liu在分布式计算领域的专家。
可以看出，这位Yanhong A. Liu对tau作出了较好的评价。
Dear Ohad,
your tau sounds great, and even IDNI too!
However, for arbitrary negation, PFP is not good, because it gives no
good guarantees, not even termination if you test only adjacent
iterations.
Instead, you may want founded semantics
(https://arxiv.org/abs/1606.06269), the simplest that gives the best
of everything:)
I have a long story before it appeared in LFCS last year (and it
appears so much more complex than it is for crazy reasons),
but my goal was not at all the semantics but efficient computation (as
efficient as no negation), except I've not since gotten back to
publishing the writing of the algorithm:(
Actually, the delay was mostly because I worked more on distributed
algorithms, especially consensus
(http://www.podc.org/podc2019/workshops-and-tutorials/tutorial-descriptions)
and our language DistAlgo (many extensions).
I wonder what consensus algorithm IDNI uses.
Also, your grand scheme sounds marvelous, that I had too but did not
speak; in fact I always told my students it's for next life:),
although we might be getting started...
Implementing in C/C++ has been my plan for another next life! as well
as in js for a playground the web:)
Perhaps you will realize even more exciting dreams of mine, that have
started to consume my time more...
Best, Annie
tauchain老大的回复邮件如下
Thank you so much Annie, I'll surely go over your materials. The reason I chose PFP is because it's more expressive than the well founded semantics which is just PTIME complete, and we'll also be able to use the wfs if we like, as below where I detail the metalanguage argument. And sure I'll have to store the kb in all states and not just adjacent states, and here BDDs play a great role thanks to their
cannonicity, so I only have to check if two BDD identifiers are equal. Another somehow deeper reason for PFP is as follows:
Let's ask ourselves "what should be the language of law". Well, we can think of 3 requirements:
1. Decidability. If we cannot decide what is legal or not, that'd be a problem.
2. Self-reference, or in other words arbitrary recursion. Suppose we have laws, great, now we also need laws of changing the laws, otherwise anyone can just change the laws. But then we'll need also laws of changing the laws of changing the laws, which will never end. We therefore need a logic that supports feeding the law into itself and deciding whether it's legal. This cannot be achieved in total
languages, and in fact seems to be achievable precisely for Turing complete, P-complete, PSPACE-complete, or ELEMENTARY (PFP can capture ELEMENTARY if we allow to sequence several PFP programs where one takes as input the trace [or proof] of the other).
3. Ability to delete rules, as sometimes we'd like to legislate a rule that contradicts an old rule, hence things have to be nonmonotonic.
Requirements 1+2 leave us with P,PSPACE,ELEMENTARY. But requirement 3 leaves us only with PSPACE and ELEMENTARY.
Another similar argument (although it holds for P as well but we surely prefer more expressiveness as in PSPACE):
1. We postulate that there isn't one language which is adequate for all needs whatsoever.
2. We therefore come up with a metalanguage that defines other languages.
3. But that'd be back to square one - having one metalanguage to rule them all.
4. Therefore we require the metalanguage to be able to define its own semantics and be able to change itself.
This leaves us with Turing complete, P, PSPACE, or ELEMENTARY as above. Taking another requirement takes Turing out:
5. We want to be able to go back and forth between languages, so if the metalanguage define how to translate from language X to language Y, we can get "for free" a translator from language Y to language X. I won't be surprised (though don't know for sure) if this requirement 5 leaves out P as well.
I'll be very glad for cooperation with you.
Best Regards,
网友评论