On State and State Space

computer science, computer science theory

A profoundly influential idea, but

While the notion of state has been a profound influence on intellectual progress as a basis of mathematical rigor and mechanism of truth it has also been a barrier to progress. The problem is that for any behavior to which state space is being applied the behavior must conform to the demands of the state space. Put another way, reality must conform to the demands of the model instead of the model conforming to the actualities of reality; concurrent behaviors, for instance, must be sequenced. This is why computer science is a diaphanous castle in the clouds with no founding in reality. 

The notion of state and state space

A state is a particular condition of differentness from a range of possible conditions of differentness of a particular manifestation of state. There may be many particular manifestations of state forming a space of manifest states. Typically the range of possible conditions of differentness are shared among manifestations of state, numeric values for instance, allowing the possibility of identical conditions of differentness among states. Condition of differentness does not uniquely individuate a state so each manifestation of state is further individuated with a unique identity in the state space which may or may not involve a notion of structure of the state space. This state space individuation of each manifestation of state does not change while the content of each state can change. A state sample is of all manifestations of state in the state space with each’s condition of differentness.

A state space must be constant

The state space remains constant with a population of state manifestations retaining their unique spatial individuation. It is the constancy of the state space that allows an external sampling agency to orient to the internal progress of the change behavior and to inspect the state of the state space state manifestation by state manifestation. There must be a referential constancy between the change behavior and the sampling agency.

The imposition

A change behavior can change the condition of differentness of state manifestations but may not change the spatial individuation of the state manifestations.

A state space must be determinate

To have a predicted state to compare to a sampled state the change behavior must be deterministic in relation to the state space. 

The imposition

A change behavior cannot change states with indeterminate conditions of differentness.

A sampled state space must be stable

A state space can be reliably sampled only when all of its states are stable, i.e.,when no state is in the midst of change. A sampling agency must be able to discern from the change behavior when a stable sample can be taken or it must control the change behavior to establish a stable samplable state space. The change behavior may be halted and its internal state space inspected. Or the internal state space may be extracted from the change behavior and inspected externally. In either case the sampling must be of a stable state space relative to the change behavior.

The imposition

The change behavior must explicitly make available intervals of stable state or it must submit to an external control that can establish a stable state space. The first order appraoch is for a change behavior to be one state change “at a time” sequential in that each change is completed before the next change is begun. Halted after the completion of any state change the change behavior presents a stable state until it is restarted. A change behavior can halt itself or the external agency can halt it.

State space sampling must be coordinated

If there is a predicted state to compare to a sampled state the sampling must be specifically coordinated to the progress of the change behavior. This requires coordination between the sampling agency and the change behavior.

The imposition

A change behavior must accommodate the coordination of sampling by providing a behavior discernible by the sampling agency at the appropriate state change.

There can be no concurrency

If a change behavior changes multiple states “at any time” it presents concurrent uncoordinated state change with no intrinsically discernible instants of stable state that offer opportunity for sampling and with no ordered occurrence of state changes that allows coordination of any specific state change to a specific sampled state.

The implication

The notion of state space fails in the context of concurrent change behavior. A concurrent change behavior clearly has internal manifestations of conditions of differentness and just as clearly the notion of state and state space cannot account them.

The imposition

Concurrent behavior cannot be allowed. All concurrent behavior must be mapped to sequential behavior.

The convenient street lamp

Computer science has never confronted concurrency directly but has always tried to characterize it in terms of sequentiality, that convenient street lamp at the end of the dark alley discouraging one from looking into the alley.

Internalization

Conforming all change behaviors to these impositions of observational needs leads to an internal samplable state space becoming viewed as endemic to all change behaviors whether the behavior might be sampled or whether it is even samplable. This internalization of state space is embodied by the Turing machine in its state machine and its paper tape. Change behaviors that do not conform, such as concurrent behaviors and neural networks do not qualify.

The humans in the works

The notion of state space is about making sense for humans. The state space and being able to sample it is a most convenient way to externally consider, talk of, observe, control and understand a change behavior and humans explicitly constrain and form a change behavior for it to be conveniently characterizable and observable.

The notion of state space is deeply embedded in our intellectual culture and is difficult to transcend but transcended it must be. The humans must be removed from the works. There are more general ways to account change behavior that encompass concurrency and much more.

Karl Fant

Subtleties of primitivity

computer science

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.