A comparative study of structure theories

The most groundbreaking work in the computer industry was essentially done in the late 1950s to the 1960s, because there wasn't much ground to break yet. The Algebraic Structure Theory of Sequential Machines (1966) owes its origin to that era. Every single computer science treatise now owes something to that time, and most ones have broad similarity to something back then. But the similarities often end there, as examinations of any modern theory always exposes key differences.

That is also the case with the topos theory of computations. While the basic intuitive framework is the same as Hartmanis and Stearns, all technical aspects of the theory are different. In 2023, a preliminary research paper Toposic Structure Theory of Computations (2023) was released with this new and updated theory. If this is well recieved, a full textbook on the the topos of computation, containing the advanced theory, will be produced.

With these two structure theories now widely available for consideration, it is high time that a comparative study was conducted to highlight their similarities and differences. In this study, we will describe why it is so necessary that a new and updated theory should be produced. The value brought about by the application of new techniques in categorical logic and topos theory will be described and the limitations of the classical theory will be considered.

Background and motivation:
The theory of Hartmanis and Stearns was designed with engineering applications in mind. To quote their text, "The engineering motivations demands new mathematical techniques to be invented with no counterpart in the development of algebra. Thus, this theory has a characteristic flavour and mathematical identity of its own." As a consequence, they developed the idea of information flows with its engineering applications in mind.

On the other hand, the Toposic Structure Theory of Computations (2023) is a purely mathematical treatise. It was created with the idea of exploring an aspect of topos theory in mind. That the topos it studies happens to be the topos of computations is a convenient coincidence, that makes this study worthy of publication and wide spread dissemination. This text should be of interest even to pure mathematicians working in topos theory.

Scope:
The Algebraic Structure Theory of Sequential Machines (1966) studies information flows with respect to sequential machines. These are treated as transition functions $\delta: S \times I \to S$ on a set of states $S$ and a set of inputs $I$. In effect, however, they are families of functions $\delta : S \to S$ for each $i \in I$. Then a partition pair of $\delta$ for $(P,Q)$ says that for each $i \in I$ : $s =_P t \Rightarrow \delta(i,s) =_Q \delta(i,t)$.

They never consider to examine what a partition pair $(P,Q)$ be defined an a single function $f: A \to B$ would mean. Already in section 0.1 of their text, on "sets and functions" you can see that they are hopelessly lost in the old ways of set theory. The great mental liberation and significant technical advantages of modern topos theory were not considered.

That is why they define information flows always for families of functions $\delta_i$ rather then considering them individually. If they'd taken the later perspective, their theory would have had better foundations. This approach produces a theory with very limited scope and applicability. It is no wonder then why this theory was hardly ever used and history went the way it did.

By contrast, the Toposic Structure Theory of Computations (2023) is applicable to any kind of functional computation. This produces a theory with far greater and wider applicability than ever before, and it exposes all functions to the logic of information flows. This is really a paradigm shift and a transition from foundations in the topos $Sets$ to the topos $Sets^{\to}$.

Mathematical context:
In the Toposic Structure Theory of Computations (2023) we study the topos $Sets^{\to}$ and its morphisms. These are ordered pairs of functions $(i,o)$ between functions $f$ and $g$ that form commutative diagrams like so: Then $(i,o)$ has an epi-mono factorisation like so: There are your partition pairs $(P,Q)$ emerging right out of morphisms in the Sierpinski topos. They exist between individual functions. A morphism in the topos $Sets^{\to}$ is the embedding of the information flow of some function in another. The algebraic approach to information, it turns out, is nothing more then the logic of the topos $Sets^{\to}$.

By taking this categorical perspective we are able to create a far richer theory than the classical one of Hartmanis and Stearns. The effects of morphisms in $Sets^{\to}$ on information flows is considered categorically, leading to a number of interesting results. Functorial semantics for information flows are developed. None of this would be possible without the use of new developments in category theory.

Conclusions:
The prior work of Hartmanis and Stearns on the algebraic theory of information is inspiring. Any further work in the algebraic theory of information should mention their fundamental work and give proper credit where it is due. Nonetheless, their approach is frought with a number of limitations: limited scope, a lack of category theory, underdeveloped mathematical foundations. This is solved by creating a new theory.

References:
[1] Hartmanis, J., & Stearns, R. E. (1966). Algebraic structure theory of sequential machines. Prentice-Hall.