chemSKI with tokens: world building and economy in the SKI universe
This provides a solution for decentralized graphical reduction in combinatory calculus, though it appears incremental as an extension of existing SKI and chemical graph rewrite concepts.
The paper tackles the problem of performing SKI calculus reductions in a distributed, decentralized manner by introducing chemSKI with tokens, a confluent graph rewrite system with local and conservative rewrites, resulting in a new estimation of computation cost and enabling use as an artificial chemistry or virtual decentralized machine.
chemSKI with tokens is a confluent graph rewrite system where all rewrites are local, which moreover can be used to do SKI calculus reductions. The graph rewrites of chemSKI are made conservative by the use of tokens. We thus achieve several goals: conservative rewrites in a chemical style, a solution to the problem of new edge names in a distributed, decentralized graphical reduction and a new estimation of the cost of a combinatory calculus computation. This formalism can be used either as an artificial chemistry or as a model of a virtual decentralized machine which performs only local reductions. A programs repository and the same article with simulations are available at github at https://mbuliga.github.io/chemski/chemski-with-tokens.html