This post is chapter 1 of my latest essay “A Journey Through Computation: Natural and Human” which lays the groundwork of a theory of computation in terms of dependency and concurrency in contrast to control and sequentiality.
Chapter 1: Subtleties of primitivity
Sequence controlled steps of behavior, considered fundamental to 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, express a computation. A sequence of steps has to express the correct flow of dependency relations through the state environment. Dependency of flow relations include relations that can occur “all at once” or “in any order”. The, “all at once”, represents concurrent relations. The, “in any order”, means that the concurrent relations 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 express the concurrent relations of the flow of dependency relations. Further, there is a multitude of sequential orders that do not correctly express the flow of 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 expressing the correct flow of dependency relations corresponding to 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 network expression with its innate concurrent relations.
1.2. QUANDARY 1: Sequential expression is not primitive
Sequential ordering necessarily derives from dependency relations with their innate concurrency. 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. Sequencing 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. The mathematician with her pencil and paper is the original sequence controller. In the absence of the mathematician a sequence controller must be devised. A sequence controller might be devised as a sequence of more primitive behavior steps controlled by a more primitive sequence controller which in turn might be devised as a sequence of even more primitive behavior steps controlled by a even 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 expressed in terms of a controlled sequence of steps.
1.3. QUANDARY 2: Sequence control is not primitive
Sequence control which cannot express a most primitive sequence controller cannot be primitive. The most primitive sequence controller cannot itself be sequence controlled but must be expressed in terms of dependency relations among primitive behaviors which innately include concurrent dependency relations.
1.3.1. 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.4. Boolean logic
Boolean logic behaviors, conventionally understood to be most primitive behaviors, are placed in a network of dependency relations with its innate concurrency relations. The enlivened Boolean behaviors 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, which will be presented to subsequent behaviors causing them to temporarily transition their output to incorrect result transitions. Glitches will race ahead though the network of behaviors asserting a chaos of incorrect transitions at the output of the network. The dependency network with its Boolean behaviors cannot, on its own, determine amidst the chaotic transitioning of incorrect results when the correct result of the presented input occurs. This chaotic transitioning through concurrent relations is the Pandora’s box of non determinacy mentioned in the quote above.
1.4.1. Hiding the chaos of concurrency
If the inputs to a Boolean logic dependency network are held stably for long enough correct results eventually propagate through the behaviors and the network stabilizes asserting the correct output for the presented input. The chaotic behavior of a Boolean logic dependency network can be hidden and remediated by isolating and bounding it with memories 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 and an output memory ignores the output of the network. At the end of the time interval the output memory is enabled to accept the correct and stable output of the network. The chaotic concurrent behavior of the Boolean dependency network is isolated and hidden within the time interval and between the bounding memories. The deterministic expressivity of the Boolean dependency network is recovered but the dependency relations and their Boolean behaviors cannot compose beyond the time interval. From this point on composition is in terms of time intervals.
1.5. QUANDARY 3: Boolean logic is not primitive
A network of dependently related Boolean logic behaviors is not primitive. The Boolean logic behaviors, on their own behavioral merits, are insufficiently expressive to coordinate the innate concurrent relations of the dependency network and require the extrinsic expressional support of a time interval with memories.
1.5.1. Sequential steps of hidden concurrency
The Boolean dependency networks bounded by the clock are composed into a greater network of Boolean subnetworks all timed with the same time interval long enough to accommodate the slowest to stabilize subnetwork (critical path) behave concurrently (all at once) within each time interval (synchronously). The single common time interval precisely controlling the start and end of all the concurrently behaving subnetworks fulfills the above author’s requirement of precisely controlled relative speeds for reliable concurrent behavior.
The control of the clock overcomes the problematic concurrency behaviors of the Boolean dependency network and enables the concurrent behavior of the composed subnetworks. In this way a most primitive sequence controller can be realized establishing sequential expression and sequence control.
1.6. QUANDARY 4: Confusions of primitivity
Sequence is not primitive. Sequence control is not primitive. A dependency network of Boolean logic behaviors is not primitive. Dependency relations while appearing to be primitive present chaotic concurrencies. The sequencing control of the clock overcomes the concurrency chaos allowing the realization of the most primitive sequence controller which enables sequential expression and interpretation. One could argue that sequence control is necessary and fundamental if not primitive. Yet the expression of sequenced steps at all levels still derives from and is preceded by dependency relations with their innate concurrency. Dependency relations with chaotic concurrency linger within each clock bounded Boolean logic network. Dependency relations still underly everything.
1.6.1. Why Boolean logic?
Boolean logic is considered primitive to computation because it is considered mathematically primitive. In timeless mathematics the timing problems with concurrency do not arise. Furthermore, the arbitrarily expressive mathematician can realize a Boolean logic dependency expression step by step through time with her pencil and paper. She knows when new input data is present and when the output is done. She also knows to have the inputs to a concurrent relation resolved before resolving the concurrent relation. In particular she expresses temporal occurrence and temporal completeness in relation to the Boolean logic dependency network. Her time stepped Boolean network works just fine.
1.6.2. Boolean logic on its own
But a Boolean logic dependency network on its own without the mathematician’s expression of temporal occurrence and temporal completeness relations cannot negotiate the concurrent relations of the dependency network. Boolean logic considered Mathematically fundamental can’t be responsible for the chaotic behaviors. It must be the concurrency of the dependency relations. This unfortunate but unavoidable aspect of reality is an engineering problem, not a math problem.
1.6.3. The expressional crux of the primitivity matter
The Boolean behaviors are composed into a dependency network. The clock interval is imposed isolating the Boolean behaviors preventing them from further composing. The unit of further composition becomes the time interval itself. There is an incoherent midcourse discontinuity in form of expressivity from composing dependency relations among Boolean behaviors to composing in terms of time steps. This practical scheme works and has supported the phenomenal development of computing over the last 80 years. But the incoherent midcourse discontinuity in form of expression precludes a coherent accounting of computation.
There is a failure of primitivity either with the concurrencies of the dependency relations or with the insufficient expressivity of the Boolean logic behaviors or perhaps there simply is no viable primitivity of computation.
1.6.4. Coherently accounting computation
The journey discovers that there is, indeed, a viable primitivity of computation with primitive behaviors expressing temporal occurrence and temporal completeness that determinately realize the concurrent dependency relations as did the mathematician with her pencil and paper. Primitive behaviors that compose to greater expressivity on their own expressional merits.
Given the existence of sufficiently expressive primitive behaviors that can deterministically negotiate the concurrency relations of the dependency network it follows that the Boolean logic behaviors, out of their expressional depth with unconstrained computation time, must be considered responsible for the failure of computational primitivity that necessitated the intervention of the clock to constrain time.
The journey discovers and explores:
a context of accounting computation in which there is no discontinuity in form of expressivity,
a context in which a primitivity with intrinsic concurrency is sufficiently expressive to support deterministic composition to indefinite complexity with no need of extrinsic intervention,
a context of dependency relations with their innate concurrency in contrast to a context of sequence relations disregarding concurrency,
a context in which time is a fully vested citizen of expression in contrast to an externally imposed mandate,
a context of timeful computation in contrast to a context of timeless mathematics,
a context of dependency and concurrency in contrast to a context of control and sequentiality,
a context of spontaneously flowing wavefronts of transition in contrast to a context of controlled steps of state update,
a context in which controlled sequence emerges from dependent concurrency in contrast to a context in which dependent concurrency emerges from controlled sequence,
a context providing a common characterization of computation whether in a biological cell, in a digital computer or in a mathematician’s thoughts,
a context within which familiar forms of computation, Boolean logic with its time interval, place value number with its arithmetic and sequential interpretation with its notions of control and state, emerge through considerations quite different from those of their historic development.
If you have gotten this far and are still interested the journey continues at https://www.karlfant.net
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.