Algebraic structure theory of sequential machines

What Hacker News says

1. 082349872349872Jan 2023
   You may be interested in: Hartmanis & Stearns, Algebraic Structure Theory of Sequential Machines (1966)
   thread
2. johnbernierJan 2023
   Upon review, Hartmanis and Stearns appear to have come closest to my work. I would recommend readers take a look at Algebraic Structure Theory of Sequential Machines (1966) prior to my paper to get a background motivation for my treatment of the subject. The idea of partition pairs in that textbook coincides with epimorphism classes in the Sierpinski topos.

   So basically, all I am doing is updating that prior work and turning it into a Topos Structure Theory of Sequential Machines. I arrived at the concept of partition pairs independently through the Sierpinski topos. Hartmans & Stearns came up with the same idea for its engineering applications. It often happens that when an idea is good, it tends to crop up independently in multiple different places.

   Show morethread
3. 082349872349872Jul 2025
   Love the autobio.

   Noise and the differential reminds me of Hartmanis & Stearns, Algebraic Structure Theory of Sequential Machines (1966), in that the latter roughly studied how our knowledge of what state an automaton is in diffuses over repeated transitions.

   thread
4. johnbernierFeb 2023
   That works for any function f that is precomposed by a bijection. Then the bijection and its inverse cancel out, so that is correct. Many of these examples with regards to precomposition and postcomposition might be embedded in other categories, such as slice categories: C/f or f/C. However, of all the different categories you can use to make a model of functions I have singled out Sets^(->) because it forms a topos.

   The property that Sets^(->) is a topos gives us a lot to work with. All impredicative constructive mathematics can be defined internal to Sets^(->). This is interesting because it means almost all mathematics can be done internal to Sets^(->), with functions instead of sets as its first class logical objects.

   Secondly, the fact that it is a topos gives us an internal logic in Sets^(->). The internal logic of Sets^(->) is a trivalent logic with three values: true, false, and half truth that fails to satisfy the law of excluded middle. Sets^(->) has its own distinct system of logical operators and connectives which generalize those in classical logic and that can be used on all subobjects.

   All aside from that, Sets^(->) has an incredibly remarkable logic of quotients. It has been shown that the dual logic of quotients in Sets^(->) is intuitively similar to the partition pairs construction of Hartmanis and Stearns in Algebraic Structure Theory of Sequential Machines (1966). So the immense power of the topos Sets^(->) is enough to capture their central construction for creating a computational structure theory, and mine.

   All this demonstrates that Sets^(->) by itself has an incredibly rich theory which is worthy of further exploration. The theory of Sets^(->) is really the functional counterpart of set theoretic foundations, a foundation for a different kind of function-based mathematics, and the means by which we can create a system of logical reasoning for functional programs.

   [1] https://ncatlab.org/nlab/show/topos

   [2] https://ncatlab.org/nlab/show/internalization

   [3] https://ncatlab.org/nlab/show/internal+logic

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

   Show morethread
5. johnbernierJan 2023
   The basic idea of an information flow was introduced by Hartmanis and Stearns in the algebraic structure theory of sequential machines. This is a beautiful and elegant formalism for describing how information flows in sequential machines. Now using new mathematics I have put this theory on its highest level of generality. But its not enough that this should be a mathematical theory, so I also discuss its implementation.

   At the center of an implementation of information flows is the idea of a partition image. This codifies how a particular function maps a piece of information into some other piece of information. To implement this intuitive idea, I define a type hierarchy of different partition and function classes and use multiple dispatch on them to determine the right algorithm to use on a case-by-case basis.

   Show morethread