We give details of an application implemented using an Incubator. It consists of a simple calculator which is able to perform arithmetic computations. The Incubator is fed a string (in the form of a ligand) which contains numbers and arithmetic operation symbols (+, -, * and /, along with parentheses), and reduces the string to its result by the action of multiple arithmetic processing units, if the string is well-formed. When reduced to a single number, the string is output as the result. Many processing units participate in the computation. We list them here:
The harness required for the calculator is very simple. It first instantiates the Incubator and populates it with the appropriate processing units. It then prompts a human user for a string to evaluate, attaches BEGIN and END markers to the string, and feeds it to the Incubator. Finally, it waits for the end of computation to be signaled by the end detector, or for a specified timeout. It then cleans up and loops again from the beginning.
For example, when fed with the string
(2 + 2) * (3 + 2 * 6 + 5)
it will output 80. “We've come so far!”, you exclaim. Indeed, this calculator probably wins the prize for the most lines of code written to perform simple arithmetic computations. However, one should not lose sight of the fact that the entire Incubator apparatus is independent of the application. The “calculating” part of the program is indeed quite small, and consists in the specifications of the individual processing units and a harness for user interaction. This specification may be compared with giving an input file to a yacc-type program to specify the calculator.
There are three main differences, however, with how such a “classical” calculator would be programmed. Namely: the Incubator-based calculator goes through an arguably unpredictable sequence of states; it is intrinsically parallel; its behavior in the face of an invalid input string is to go in a loop. We examine each of these characteristics in turn.
Consider the example above. A possible reduction sequence is the following:
(2 + 2) * (3 + 2 * 6 + 5)
(4) * (3 + 2 * 6 + 5)
4 * (3 + 2 * 6 + 5)
4 * (3 + 12 + 5)
4 * (15 + 5)
4 * (20)
4 * 20
80
However, another, slightly different reduction sequence is possible as well:
(2 + 2) * (3 + 2 * 6 + 5)
(4) * (3 + 2 * 6 + 5)
4 * (3 + 2 * 6 + 5)
4 * (3 + 12 + 5)
4 * (3 + 17)
4 * (20)
4 * 20
80
(There are other orders as well.) As far as the processing units are concerned, which sequence is executed first is impossible to predict. For any classical implementation of the Incubator (on traditional PC hardware, for instance), the order is well-determined, but it is buried in the Incubator — even deeper, in fact, since the Incubator relies on the OS's random number generator to determine the matching order.
Obviously, since the execution order is impossible to predict (beyond the clues provided by matching), it needs to be immaterial. This requirement applies to the writer of the processing units. It can be verified easily that the processing units described above satisfy this criterion for any input ligand. We discuss this further in the next section.
Consider the following initial sequence:
(2 + 2) * (3 + 2 * 6 + 5)
(2 + 2) * (3 + 12 + 5)
There are three possibilities to consider as the next step. Furthermore, some of those possibilities are independent in the sense that they can take place at the same time without affecting the result. In fact, if we consider that two processing unit interactions take place at the same time, we can go in a single step from the last state above to either one of the following two states:
(4) * (15 + 5)
or
(4) * (3 + 17)
Of course, parallelization and sequence unpredictability are closely related in that parallelizability also implies an awareness on the part of the resident programmer. In fact, both are manifestations of the same principle: that there is no well-defined time line in the Incubator, and no need for one. Rather, there is a partial ordering on the various events that can take place. Finally, let's consider the behavior of the above-defined Incubator in the face of an invalid input ligand. For instance, suppose we feed the string
5 + 3 * + 2 + 1
The Incubator can perform one reduction to
5 + 3 * + 3
but no processing unit matches any fragment of this new string. In this case, the Incubator simply stalls — the ligand, in some sense, is not digestible (we'll come back to this analogy later when we discuss the Cytoplasm). However, all is not lost — there are different ways to make this situation explicit. One is to add further processing units which detect invalid conditions and abort the computation, reporting an error. For instance, all of the following patterns are invalid:
+ END
- END
* END
BEGIN +
BEGIN *
* +
+ *
- *
<num> (
) <num>
...
This makes for a lot of extra processing units (or for a single, compound one which matches different patterns), and it's difficult to figure out if we've really exhausted the entire list of possibilities without going through a formal analysis of the reductions and possible inputs. Furthermore, this solution is biologically improbable, a subject to which we will return.
Another possibility to help detect an invalid ligand is to have the Incubator notify some resident when further matching is impossible - to have some kind of default behavior when all the registered matches fail. This solution is akin to what one would do with a traditional yacc-type input file. However, one difficulty with this scheme is that instead of having a situation where matching is impossible, we may have an infinite cycle. It can be shown easily that there are no cycles possible in the above Incubator (the effective string length diminishes with every processing unit application — FIXME: This may change when introducing rational division), but we can envision easily a situation where they are possible. Imagine that we add a processing unit to the Incubator which embodies commutativity of addition. It detects patterns of the form [+|-|BEGIN|(]<anything1>+<anything2>[+|-|END|)] and switches the order of the operands (note that anything is not quite anything — needs to contain balanced parentheses, for one). Then the above sequence can quickly change into
3 * + 5 + 3
3 * + 8
and thence oscillate between the latter string and
8 + 3 *
In this case, matching will always be possible, which makes the situation difficult to detect, but no “progress” is made. Of course, this situation is very much akin to an infinite loop in traditional programming. Detecting these oscillations is in fact a sub-problem of the halting problem for general Turing machines, hence is theoretically intractable. It is up to the resident programmer to ensure that the set of residents in the Incubator does not encode such cycles. Note that the cycles can take place even if the input ligand is valid (as is the case with the above commutation processing unit, for instance).