Let us make a number of definitions. We call a set of processing units a program. (Duplicate processing units in the same program very well may affect the outcome of the computation - they will certainly affect performance.) An Incubator equipped with a program but containing no ligand is called a primed Incubator. An Incubator is said to be at rest if there is no matching possible. It is said to be grounded if there are no bindings. A program is well-grounded if and Incubator primed with the program is at rest and grounded when there are no ligands present in the Incubator. We concentrate initially on well-grounded Incubators because their dynamics are simpler to explain. The notion of input for an Incubator is easy to define, at least for a well-grounded Incubator. The input to an Incubator is simply a ligand which is fed to the Incubator. However, the output is somewhat more ambiguous to define. When fed with an input, a primed Incubator may perform operations indefinitely (we will relate this to the Halting problem in the next section). Hence we must make a few additional definitions. A ligand is said to be terminating with respect to a certain program if an Incubator, primed with the program and initially grounded and at rest (if possible) eventually reaches rest again after being fed the ligand at input. Even in this case, however, it is not necessarily the case that there is an identifiable output to the Incubator: to identify an output is a role of the program, and it might fail to do so. Note that we can't simply refer to “the transformed input ligand”, since that ligand might be transformed beyond identification (it might have been split into many fragments, it might be bound, it might simply be gone). To identify an output to the Incubator is a collaborative task of the program and of the harness. The program must send some kind of signal to the harness, and allow the harness to extract the output (and, possibly, reset the Incubator to its ground state). A ligand is semantically terminating with respect to a program and a certain harness if it is terminating and if it explicitly designates an output to the harness, as described above. We won't explore this notion further in the present chapter. A program is said to be behaved if it is well-grounded and if all ligands are terminating with respect to it. Even if a program is behaved, as above, it can act very badly: it can give different results at different times for the same input ligand, unpredictably, because of the probabilistic nature of matching in the underlying Swarm. For instance, consider two behaved programs P1 and P2. It is easy to construct a new (behaved) program P which, when fed any ligand, will compute either P1 or P2 applied to it, unpredictably (FIXME: Show how).
It is important to realize that this non-determinism is a fundamental property of the Incubator — or rather, of the underlying Swarm. It is independent of the implementation of the Swarm layer. Even if the Swarm is implemented using completely deterministic algorithms — as it currently is, using a standard random number generator — the processing unit programmer can not rely on any determinism. The Incubator is completely decoupled from the program inasmuch as matching is concerned, which means the non-determinism must be assumed even if it is illusory. (In other words, “you can't rely on something you can't rely on”.) Rather, determinism becomes a property of the program, if we make the following definition: a behaved program is deterministic if it always reaches essentially the same end state at rest when fed, from the ground state, the same ligand. (FIXME: We need to characterize exactly what “essentially” means. If the program is semantically terminating, it means that the output is the same. But otherwise it's a little bit more fuzzy.) Hence, this situation contrasts sharply with regular programming of modern computers, where determinism is never in question (except in case of breakdown). We claim that the non-determinism introduced by the matching process participates in a profoundly essential way in the other non-classical properties exhibited by Monod — adaptability, pattern recognition, etc., as we hope to show later. A so-called trade-off principle — between deterministic programmability, efficiency and adaptability — has been discussed elsewhere:
“A system cannot at the same time be effectively programmable at the level of structure, amenable to evolution by variation and selection, and computationally efficient.”[Michael Conrad, quotation in Sienko et al. 2003, p. 146].
The attentive reader will have noticed that we have skirted a subtle point: is the property of being behaved actually deterministic? As we've defined it, there's no ambiguity: a behaved program always (deterministically) reaches rest. However, it is easy to conceive of programs which are probabilistically behaved but otherwise deterministic — that is, they terminate with a non-zero probability, but when they do, they always yield the same result. Indeed, for any deterministic program P, consider the alternative program P' which consists of P with the addition of a simple processing unit which matches any input ligand in its entirety and releases it immediately without modifying it. It is for this new program to stall by repeatedly binding with the new processing unit and never invoking the original program P. However, as soon as the original ligand is modified by P — which may happen at any time — the new processing unit is out of the loop, and the Incubator will reach the resting state prescribed by P.
We have avoided another issue, this one more important: how do we account for the possible role of the harness in releasing bindings? This role might be crucial. We have up to now assumed that the processing units are entirely responsible for the binding releases (as was the case in the calculator example above). At the other extreme, however, the harness could be responsible for all releases if the individual processing units ask it to perform the releases, for example. This makes all the above definitions useless — unless we recast them relative to a given harness. Hence, we introduce the notions of an h-behaved program, h-deterministic program, etc., all relative to a certain harness. Note that a program can be h-deterministic with respect to two different harnesses, yet yield different outputs for each harness — it can do so even if it is deterministic! The theoretical situation can thus occasionally be difficult to understand. The use of harness-controlled release will be made apparent when we discuss the Cytoplasm layer later on.
Let us consider the calculator example given in a previous section. The first incarnation of the calculator program, where the program Pcalc1 consists of operational processing units only, is certainly well-grounded. All valid ligands are terminating (and in fact, are semantically terminating with respect to the harness provided) — however, invalid ligands are not terminating, so that the program is not behaved. Adding the processing units to handle all the invalid cases, as we do later, makes the new program Pcalc2 behaved. It is also easy to verify that it is in fact deterministic - as it should be if it is to be a reliable calculator.
FIXME: Is determinism truly a desirable property, always?
FIXME: When we have another example, we have to discuss it as well.