This is an excerpt from
Molecular computers which are based on graph rewriting systems like chemlambda, chemSKI or Interaction Combinators (v1.0.0). Zenodo. https://doi.org/10.5281/zenodo.7306917
with some comments [added between square brackets].
This is related to chemSKI not Kind, chemSKI not Nock, as well as ZSS: Zipper logic revisited and Asemantic computing.
Your comments are welcomed! Please use cites to specific arguments of mine or others. Please don’t use partial arguments without cites, nor impressionistic formulations like “I don’t see why/where/how …” 🙂
The gist of it: in Nature or Decentralized Computing we have to learn to understand or deal with only local computations.
Here is the commented excerpt.
Typically there is a 3 stages process which uses graph rewriting. We want to solve a problem, therefore we write a program.
- meaning to structure: The program is then compiled to a graph. This can also be seen as a language to structure problem. The language can be a term rewrite system, the program can be a term, the structure can be an abstract syntax tree. Many other examples exist, which can be put into the form of transforming something which has a meaning (for a human), to something which can be processed by a machine (in this case a graph).
- structure to structure: transform the initial graph into a final graph, by using the graph rewriting system and an algorithm for the choice and order of application of the rewrites. Usually this problem is complicated because we want to have a good translation not only of the meaning to structure, but also of the term reduction into graph reduction. For example, when we write a program we expect it to “do” something, and we would like that the execution of the program by the machine (ie the structure to structure part) to be a translation of what we imagine the program is doing. As an example, if our program is a lambda term, which is compiled into a graph, we would like the graph rewriting to be compatible with the term rewriting, ie the beta reduction term rewriting rule. These semantic constraints which are put in the use of graph rewriting are incompatible with decentralized computing, see Asemantic computing
- structure to meaning: transform the final graph into the language, in order to obtain the answer of the problem. For example, if the initial program was a lambda term, we compile it into a graph, then we reduce the graph, then we translate back the final graph into a lambda term. In other examples we just want to translate the final graph into something which has a meaning for us, into the solution of the problem.
In all such applications of graph rewriting, we position at the level of meaning, we descend at the level of structure, where we use graph rewriting as a tool and then we translate back the result into a meaningful output.
Here is a different 3 stages process, where we put the accent on the structure to structure level. As an example, we want to have a chemical molecule which can be absorbed by a living cell. We want that, once inside the living cell, the molecule is processed and produces a nano-machine (by making parts which self assemble, or by other means), all by itself and outside our control. For this kind of problem the 3 steps are:
- meaning to structure: create the initial molecule, from a high level, language specification. For example say that the input molecule will be a piece of rna, created in a lab. [In decentralized computing the input molecule would be a mol file which is created by a user and then split between a small number of users.]
- structure to structure: in the cell, the initial molecule enters in random reactions with other molecules and leads to another structure. For example the molecule is chemically copied and then translated into proteins which self-assemble into the goal nano-machine. [In decentralized computing all users apply the same reduction algorithm, thus exposing the pieces of the mol file of the small number of users to the rest of the users, in principle, and also without any synchronization among users.] We have no control over this step and there is no meaning (semantics) to be satisfied by this random process. [In the sense that there is no global in time and in space meaning which controls or survive to the local reductions.]
- structure to meaning: the presence of these nano-machines in the cell produce an effect which we can observe. [In decentralized computing, the structure to meaning function or algorithm can only be local to the user and graph (piece of mol file) the user has. Since all the global annotations of the graph are washed away in principle, the structure to meaning function has to be local as well.]
The differences are striking:
- we want to produce a structure which, left alone, induces the creation of another structure, [in decentralized computing, the small mol file or files introduced in the computation by a small number of users will produce effects which can be observed by them via a local structure to meaning function.]
- the level of meaning (where we design the initial structure in order to be able to obtain the final structure) is a tool which serves the structure to structure goal, [in decentralized computing, in order to produce a graph which has the desired effect, we perform experiments with graphs coming from a humanly understandable programming language, like for example lambda calculus. Once such a graph is build from the programming language, the experiments allow us to understand what happens at the graphical level and then to exploit the graphical level mechanism for goals which are not directly possible at the initial programming language level. Much of the chemlambda collection of simulations uses this type of exploration.]
- there is no control of the algorithm of applications of graph rewrites, it is given by the nature. [In decentralized computing, in principle, the exterior of a user’s graph and interations are random, this is the best user’s theory abvout the rest of the universe.]
chorasimilarity 