Automata dynamics modelled via monoid actions
Lulof Pirée
Tallinn University of Technology
Abstract:
Many familiar models of computation, such as Boolean circuits,
deterministic automata, Turing machines, etc., can be seen as a graph of memory
cells that change their content according to a local update rule.
The behaviour of cells over multiple steps in time depends recursively
on the behaviour of connected cells, which quickly leads to complicated
expressions in inductive proofs.
However, when viewing time as a monoid,
then coKleisli composition allows to scale local rules to arbitrary long
intervals in time.
This not only simplifies proofs, but also provides other fun
opportunities.
The talk will (1) show several examples of how familiar automata fit in the
framework, and (2) try to explain how (co)Kleisli
composition recursively computes the multi-step behaviour.
Familiarity with models of computation such as Boolean circuits and Turing
machines is assumed,
and acquaintance with (co)monads and (co)Kleisli categories is useful.