Category Archives: computer science theory

The new theory of computer science.

The Quest

computer science, computer science theory, Flow computing - hardware, Flow computing - interpreter, Flow computing - language, flow computing - model, Null Convention Logic, Questions and Answers

“Second, though, I also want to make evident just how much such a transformation costs. Politics, creativity, ambiguity, irreverence—none of these can be grafted at a later stage, onto a silent steel core, or even poured, like life-giving water, over inherently desiccated foundations. The whole story has to be turned upside down.” Brian Cantwell Smith*

Thirty year later

“In the end I argue for reconstituting the theoretical framework on which present-day computer science rests.” Brian Cantwell Smith†

Journey through the upside down story of reconstituting the theoretical framework of computation at https://www.karlfant.net.

*Smith, Brian Cantwell, On the Origin of Objects. Cambridge, MA: MIT Press, 1996. p x
†Smith, Brian Cantwell, Computational Reflections. Cambridge, MA: MIT Press, 2026. p 1

Knowing computation

computer science, computer science theory, Flow computing - hardware, Flow computing - interpreter, Flow computing - language, flow computing - model, Uncategorized,

“For most of my life I have not been able to answer these questions, because I have not known what computation is.” Brian Cantwell Smith 1

What is computation that it can be not known?
It begins with the advent of arithmetic bearing ubiquitous utility with the realization that arithmetic is a complete system of objects and rules of their manipulation that can be rote taught to a person who can then perform arithmetic without understanding what she is doing and be construed as effectively computing a function. Arithmetic can even be taught to a machine by building it to honor the objects in an indexical state and their manipulation rules construed as a digital state machine. By defining a small set of basic state manipulating rules arithmetic computation can be realized as a sequence of manipulation steps construed as an algorithm machine made with physical symbols. The contents of a state can be viewed as symbolic referents manipulated by a sequence of rule steps construed as formal symbol manipulation or as information processing.

The common theme among the construals is the manipulation of a state of objects. The intrigue is that such a simple framework can be usefully realized in so many different ways. The difficulty is that for each realization to conform to the framework the state objects and the manipulation steps are designed together; mutually defining; neither grounding; forming self contained ontological castles in the clouds. The framework is not grounded and none of its realizations are grounded.

The only commonality underlying the framework and all of its construals is the human in the works. A human intentionally invented the framework. Humans intentionally realize instances of the framework. Humans intentionally assign meanings to a state and its objects. Humans intentionally program sequences of manipulation steps for the realizations. Framework computation supervenes on the arbitrarily capable expressivity of humans who make computation whatever they want it to be.

“They (computers) are computational, of course; that much is tautological. But only when we let go of the conceit that that fact is theoretically important will we finally be able to see, without distraction—and thereby, perhaps at least partially to understand—how a structured lump of clay can sit up and think.” Brian Cantwell Smith 2

Brian clearly thinks that the universe is computing, that life is a computation. Any understanding of computation must precede the humans in the works, include an understanding of from whence they come and bear no resemblance to the conventional views of computation

“The whole story has to be turned upside down.” Brian Cantwell Smith 3

Brian did not realize how upside down the story has to be turned. You are invited on a journey of knowing computation embarking from karlfant.net. The terrain is steep with treacherous passes and fierce winds but there is no easier passage through the territory.

Karl Fant

1 Smith, Brian . Foundations of Computing. In Scheutz, Matthias (ed.), Computationalism: New Directions, Cambridge. MA: MIT Press, 2002, p. 24
2 Smith, Brian Cantwell, On the Origin of Objects. Cambridge, MA: MIT Press, 1996. p 75-76
3 Smith, Brian Cantwell, On the Origin of Objects. Cambridge, MA: MIT Press, 1996. p x

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