Computation as Semigroups, Computing Semigroups • Attila Egri-Nagy • YOW! 2018

Semigroups provide a mathematical framework for understanding and modeling computation at a fundamental level

A semigroup is a set with an associative binary operation, which can represent state transitions and transformations in computing

Full transformation semigroups contain all possible computations that can be done with n states, making them important objects for studying computational power

Computational power can be measured by analyzing the minimum number of states needed to perform specific calculations

Homomorphisms between semigroups represent the idea of emulation - one computer being able to simulate another

Idempotent operations are “safe to repeat” - performing them multiple times yields the same result as doing them once

The relationship between abstract algebra and computing provides insights into computational limits and possibilities

Finite state automata can be viewed as transformation semigroups, offering a mathematical perspective on state transitions

The study of semigroups helps understand what is computable with limited resources

Modern computers have an enormous number of possible states (2^(half a million) different states with 64k RAM), highlighting the complexity of computation