This is a belated attempt at formally delimiting what it means to be a stream complex. It would be good to be able to make precise claims but this requires precise terminology. For instance we need to reason about grid-lock and determinism. This is probably related somehow to Petri nets. Perhaps our node is what Petri net theory would call a place. One difference is that each of our nodes has some definite but unspecified behavior. Also signals between our nodes bear information. I don’t have time now to dig into other differences.

We have a directed graph (composed of nodes and arrows here). We say that an arrow is an input to a node if the node is at the head of the arrow and an output of the node if the node is at the arrow’s tail. Informally the nodes are finite state machines. Each node has some fixed behavior whose only external attribute is whether if fills some one of its empty output arrows and with which element. The graph is immutable but node state and arrow state evolve with time. Time is discrete—the value of ‘time’ is an integer. Our theory has one boolean parameter ‘d’. d=0 or d=1. I conjecture that the behavior of the complex is deterministic for d=1 and not if d=0. We would like to prove that if d=1 then the behavior of the output nodes of a deterministic complex depends only on the behavior of the behavior of the input nodes.

Take One:
There is some finite set of stream elements (such as the set of 256 bytes). At one time an arrow is either empty or (full and holds some stream element). That is the arrow’s state. Node state transition rules may require: Such a transition will empty those input arrows and fill those output arrows. To fill an arrow is to provide the stream element that the arrow holds.
This formulation precludes nodes that simply merge streams as characters arrive. We may not want to preclude this. An alternative is to allow node state transitions to depend on emptiness of input or output arrows while not being blocked on them. This permits race conditions. I am inclined to disallow node state transitions when all input arrows are empty.

The Permissible Node Behaviors

The text above comments about node behaviors. This paragraph tries to collect all limitations on such behavior. Between steps in complex time, nodes and arrows have quiescent state. The state of a node includes a bit mask with a bit for each of its input arrows and another bit mask for its output arrows. The behavior of a node can modify both of these masks on each turn. A node never gets a turn unless both masks are satisfied. A mask is satisfied when all of its bits are satisfied. An input mask bit is satisfied if its arrow is full. An output mask bit is satisfied if its arrow is empty. Each time step: Some nodes are exogenous and have no input arrows. They are input nodes. Their behavior is allowed to depend on things outside the theory, but its acts are still limited. Some nodes are exogenous and have no output arrows. They are output nodes and their behavior is allowed to effect the outside world. (They serve as input and output of the complex.) The behavior of input nodes may depend on state outside the states within the complex. Output node state transitions may be blocked on situations outside the states within the complex.

I conjecture that the indeterminate ordering of node behaviors has no external influence on the behavior of output nodes except for the order that they act. The output node behavior is dependent solely on the input node behavior.

I need to compare this with the following description of determinism: “What comes out depends only on what goes in; it does not depend on when it goes in.”. It might be good too to require that output is prompt: stuff comes out as soon as it can.

Variations on this theory would allow behavior to depend on fullness of input arrows and/or output arrows. Then the respective masks would play no role in the theory.