Join Newsletter

Computation as semigroups, computing semigroups

YOW! Lambda Jam 2018

In functional programming one might hear about the abstract algebraic concept of semigroups, at least about monoids in the context of category theory. Still, semigroups may seem as esoteric mathematical objects, although they are at the very foundation of computation.

In this talk we give an elementary definition of semigroups. As a concrete example we introduce transformation semigroups, and we show that they are natural generalizations of finite automata. This in turn leads to morphic relations (the algebraic notion of emulation) and thus to a mathematical definition of computers. Abstract algebra provides a precise language to talk about computers and programming.

The bad news is that semigroup theory is a relatively young field of mathematics, and it is full of open problems. The questions are hard, therefore we need to use computers to work on those. Somewhat ironically we can say that we use computers to understand computers. In order to show how FP helps in research, we will talk about a couple of software packages written in Clojure and GAP (a hybrid OO-FP computer algebra system) for computing with semigroups.