Sequence controlled steps of behavior, considered the fundamental model of computation, and Boolean logic, considered the most primitive computational behavior do not provide a complete and coherent accounting of computation.
1.1. Sequentiality.
“Computation is the evolution process of some environment by a sequence of “simple, local” steps.” (1)
Sequential computation is represented one step at a time. Each step is a behavior that receives an input from a state environment and returns an output to the state environment evolving the state environment step by step. Each step completes and delivers its output before the next step begins ensuring that each next step receives a stable input from a stable state environment.
1.1.1. The innate concurrency of sequentiality
A sequential ordering of steps does not, in itself, specify a computation. A sequence of steps has to realize the correct flow of dependency relations through the state environment. Dependency of flow relations includes relations that can occur “all at once” or “in any order”. The, “all at once”, represents concurrency. The, “in any order”, means that the concurrent steps can be mapped to a sequential ordering of steps. But “in any order” also means that there can be a multitude of different sequential orderings that correctly realize the flow of dependency relations of the computation. Further, there is a multitude of sequential orders that do not correctly realize the dependency relations.
Figure 1.1 Sequencing concurrency
The left of Figure 1.1 represents a network of dependency relations. In the shaded region of the network A and B can occur in any order before D. If either A or B occur after D the sequence is incorrect. C can occur in any order with A, B and D. The right of Figure 1.1 represents all the possible sequences of A, B, C and D. The shaded sequences are the eight sequential orderings realizing the correct flow of dependency derived from the similarly shaded portion of the dependency network. The unshaded 16 possible sequences are all incorrect (D occurs before A or B or both). With such variety of sequence it can be difficult to be confident of the correctness of a specific sequential order and even more difficult to reliably perceive incorrectness. The only means of differentiating a correct sequential ordering from an incorrect sequential ordering in a typically enormous set of possible sequential orderings is to refer to the unique dependency of flow representation with its innate concurrent relations.
1.2. QUANDARY 1: Dependency
Sequential ordering is necessarily derived from dependency relations so the expression of dependency relations with their innate concurrency must be considered to be more primitive than the expression of sequential order.
1.2.1. The sequence controller
Steps do not sequence themselves. Sequentiality requires a sequence controller that actualizes each step in turn, connects it with the state environment and determines its completeness of output before beginning the next step. A sequence controller cannot control itself but can be represented as a sequence of more primitive steps controlled by a more primitive sequence controller forming a hierarchy of sequence controllers such as program, instructions, microcode and so on. However, there must be a most primitive sequence controller which cannot itself be sequence controlled.
1.3. QUANDARY 2: Primitivity
Sequentiality cannot be primitive. Its most primitive sequence controller must be expressed, not in terms of a sequence of steps but directly in terms of dependency relations among primitive behaviors which dependency relations include innate concurrency relations.
That sequential interpretation provides a universal realizer of every possible computation does not necessarily mean that sequential interpretation represents a primitive essence of computation.
1.4. Concurrency
Concurrency relations are conventionally viewed from simply insignificant
“All we would lose by the omission of “parallel processing” is speed, nothing fundamental.” (2)
to fundamentally unrealizable.
“The introduction of concurrency into computation opens Pandora’s box to release the possibility of non determinacy and a host of other complications, including deadlock and livelock …. Events within concurrent systems do not necessarily occur at predetermined times, but may occur in different orders depending upon the relative speeds of different system parts. The usual assumption, which is also physically realistic, is that relative speeds cannot be controlled so precisely that the designer or programmer can depend upon them to enforce sequencing requirements.” (3)
1.5. Boolean logic
The most primitive behaviors are conventionally understood to be Boolean logic behaviors because they are primitive to a mathematician, the arbitrarily capable agency at the heart of mathematics, who can correctly interpret the behavior of a Boolean network and its concurrent relations step by step with her pencil and paper. In the absence of the mathematician, a network of Boolean logic behaviors relying on the merits of its intrinsic logical behaviors, does not work.
Enlivened Boolean functions are continually responsive to their input and are continually asserting output dependent on the input. Two behaviors, each presenting an input to a third behavior, can behave independently and concurrently with different delays. The two input transitions to the third behavior can arrive at different times causing the third behavior to temporarily output an incorrect result transition (a glitch). This temporarily incorrect result transition will be presented to subsequent behaviors causing them to temporarily transition their output to incorrect result transitions which will race ahead though the network of behaviors asserting a chaos of incorrect transitions at the output of the network. The network and its Boolean behaviors cannot, on their own, determine amidst the chaotic transitioning of incorrect results when its input has completely and stably transitioned nor when the network output is completed with the correct result of the presented input. This is the Pandora’s box of non determinacy mentioned in the quote above.
1.6. QUANDARY 3: Insufficient primitivity
Boolean logic behaviors, which are insufficiently expressive on their own behavioral merits to coordinate the innate concurrent relations in a network of dependently related Boolean logic behaviors, do not present a viable primitivity.
1.6.1. Hiding the chaos of concurrency
If the inputs to a Boolean logic network are held stably for long enough correct results eventually propagate through the behaviors and the network stabilizes asserting the complete and correct output for the presented input. The chaotic behavior of a Boolean logic combinational network can be hidden and remediated by isolating and bounding it with memories (registers – data lifeboats) controlled by a time interval long enough to allow the network to stabilize. At the beginning of the time interval an input memory presents the input to the network, the time interval waits long enough for the network to settle to a stable output then at the end of the time interval an output memory accepts the correct and stable output. The chaotic behavior of the Boolean network is isolated and hidden within the time interval and between the bounding memories.
Successive time intervals present a sequence of inputs to the network and produce a sequence of outputs. The chaotic Boolean logic network with the crutch of the bounding memories and time interval becomes a timed sequential step of determined computation.
1.6.2. Sequential steps of hidden concurrency
These memory and time interval bounded Boolean networks are composed into a network of bounded Boolean networks all timed with the same time interval long enough to accommodate the slowest to stabilize network (critical path). All of the bounded networks controlled by the same common time interval, behave concurrently (all at once) within each time interval. With the single common time interval precisely controlling the start and end of all the networks, the concurrently behaving bounded Boolean networks fulfill the above author’s requirement of precisely controlled relative speeds for reliable concurrent behavior. With each successive time interval results flow from bounded Boolean network to bounded Boolean network. The innate and chaotic concurrency relations isolated inside each bounded Boolean network are sequence controlled by the timing interval and the memories. In this way a most primitive sequence controller can be realized as a network of bounded Boolean networks all behaving concurrently and determinately to realize a single step of sequence control.
1.7. QUANDARY 4: Concurrency myopia
Timed sequence control has vanquished the chaotic concurrency of Boolean networks enabling the construction of a most primitive sequence controller. Might sequence control be considered necessary and foundational if not primitive?
Yet, even with the veneer of sequence control, the representation of sequenced steps at all levels, still derives from and is preceded by dependency relations with their innate concurrency and the most primitive sequence controller is realized with time bounded Boolean logic networks within each of which lingers the chaotic concurrency of the most primitive dependency relations.
Despite the immense computational success of sequentiality and Boolean logic over the past 70 years they fail to completely and coherently account for computation. A complete and coherent accounting of computation must embrace the primitivity of dependency relations and their innate concurrency.
1.8. Seeking a sufficient accounting
The straightforward goal of the journey is to discover an accounting of computational interaction that directly expresses dependency flow with its innate primitive concurrency relations and which evolves to encompass all forms of computational interaction. An accounting that provides a common characterization of interaction whether in a biological cell, in a digital computer or in a mathematician’s head. An accounting capable of characterizing the mathematician herself as well as what she does with her pencil and paper. An accounting from which familiar forms of interaction, Boolean logic with its time interval and sequential interpretation with its notion of state, emerge through considerations quite different from those of their historic development. An accounting of computational interaction in terms of a primitivity complete and sufficient in itself with nothing hidden and in no need of any extrinsic support.
1. Avi Wigderson “Mathematics + Computation, The theory revolutionizing technology and science”, (Princeton, New Jersey, Princeton University Press, 2019). p. 307.
2. Richard Feynman, “Feynman Lectures On Computation” (Reading, Massachusetts, Addison Wesley, 1996) p 4.
3. Charles Seitz ed., Resources in Parallel and Concurrent Systems, ACM Press, New York, 1991, introduction, page ix.