State Machines as Functors

Question

I'm looking for more examples of the following model of state machines:

in David Spivak's book on category theory, he gives in section 3.1.2.10 and in application 4.3.1.9, a description of a finite state machine in terms of category theory. The basic definition is that you fix an alphabet $\Sigma$ and take the list monoid $\mathcal{M} := (list(\Sigma), ++, [])$, then describe the state machine as a functor $X : \mathcal{M} \to \mathsf{Set}$. Given two state machines $X$ and $Y$ (described as functors), you can talk about "refinement" via natural transformations $\alpha : X \Rightarrow Y$. The story seems to end here.

This is an interesting model of state machines. I've never seen it before, and I am having trouble finding similar descriptions of state machines. I would like to see how far it has been (can be?) extended. E.g., talk about things like bisimulations, language acceptance, turing machines, computability, etc. Does anyone have more sources?

Answer 1

A very similar construction/viewpoint has been recently studied by Colcombet and Petrişan in [CP20]. They see a deterministic finite automaton as a functor $$\mathcal{A} \colon \mathcal{I} \to \mathsf{Set}$$ where $\mathcal{I}$ is the category induced by the three objects $\textsf{initial}$, $\textsf{states}$ and $\textsf{accept}$, whose morphisms are generated by:

• a morphism $i\colon \textsf{init} \to \textsf{states}$,
• a morphism $f\colon \textsf{states} \to \textsf{accept}$, and
• for each letter $a\in\Sigma$, a morphism $a\colon \textsf{states} \to \textsf{states}$.

Moreover, they add the restriction that $\mathcal{A}(\textsf{init})$ has cardinality 1, and $\mathcal{A}(\textsf{final})$ has cardinality 2. This construction is based exactly on the same idea as the one in David Spivak's book, except that his construction cannot specify initial states and final states.

One thing that is quite pleasant with this approach is that you can obtain other classical automata models by changing the category used in the codomain of $\mathcal{A}$ (and the constraints on $\mathcal{A}(\textsf{init})$ and $\mathcal{A}(\textsf{final})$). For instance, non-deterministic automata are obtained by considering the category $\mathsf{Rel}$, and weighted-automata over a field $\mathbb{K}$ by taking the category of $\mathbb{K}$-vector spaces.

A soft introduction to [CP20] can be found in [slides by Petrişan] starting from page 21. However, I do not know of any work modelling a Turing machine (or a machine with the ability to write) using the framework of category theory.