Computation as semigroups, computing semigroups
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.
Outline/Structure of the Talk
1. Basic definitions: What is a semigroup? How can a finite state automaton viewed as a semigroup? Distinction between an abstract and a concrete semigroup. What is emulation?
2. Open problems in semigroup theory that have immediate interpretations in computer science and engineering: What is the minimal number of states needed to realize a computing device? What are the distinct solutions to a computational problem?
3. Software demo: general search and orbit algorithms implemented in Clojure used for investigating semigroups (re-implementations of GAP computer algebra packages).
Participants will acquire a clear understanding of an abstract algebraic concept and its connection to computing. They will also get ideas about requirements of writing mathematical research software and how functional programming languages fit those.
They will also learn about open problems in theoretical computer science.
Anyone interested in the mathematical foundations of computation and/or curious about how functional languages are used in mathematical research.
Prerequisites for Attendees
Any FP experience, and a bit of curiosity about mathematical ideas.
Paper describing the research topic
https://github.com/egri-nagy/orbit - search and orbit algorithms
https://github.com/egri-nagy/kigen - semigroup algorithms