Paying homage to the work of Hartmanis and Stearns

A commenter alerted me to the fundamental work of Hartmanis and Stearns: Algebraic Structure Theory of Sequential Machines (1966). This came closest to capturing the fundamental ideas that I was getting at in my study of information flows. To put my work in context, I want to do something to pay homage to this prior work.

When I first thought about what to title my paper, I couldn't think of anything particularly good that would stick. So I took the good old fashioned shotgun approach and made a big title with a bit of everything: "The Topos Theory of Computing: Introduction to the Mathematics of Dataflow." Yet its clear that calling this a theory of computing doesn't get to the point, because the whole point of this thesis is an examination of structures.

By changing the title of my work to Toposic Structure Theory of Computations (2023) I get an intrinsically better title while also more effectively paying homage to the excellent prior work of Hartmanis and Stearns. This hopefully reduces any controversy around my work and puts it into an appropriate historical context. We now have two different types of structure theory in computer science:

• The algebraic structure theory
• The toposic structure theory

The Algebraic Structure Theory of Sequential Machines (1966) is one of those marvelous gems of science and technology that due to historical accident seems to have fallen to the way side. It is something that despite its age still has something to teach us, just like the Lisp machines. There is always something to be learned from studying the best technologies of the past.

But I am not here to revive old technologies. In my work, I developed novel new foundations for the mathematics of information flows using topos theory. It is demonstrated that the information flows of Hartmanis and Stearns are nothing more then quotients in $Sets^{\to}$. By establishing functors from a wide variety of different categories to $Sets^{\to}$ information flows are applied to a wider variety of contexts then ever before.

It is shown that morphisms in $Sets^{\to}$ preserve and reflect partition pairs. The result is a monotone Galois connection between information flow lattices of functions associated to every morphism in $Sets^{\to}$. This opens up a wide variety of different computations that would not be possible without the topos theoretic framework. All of this makes this subject an exciting and fertile ground for further exploration.

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