Algebraic models of local computation

A model of computation deals with two things: state and change. The later is often modeled using semigroup actions. For example, a finite state machine is defined by a semigroup action with a start state and a set of end states. In these simplest models, the state of a machine is modeled as a single set, without concern for locality. In order to model local state and change we can use lattice theory:

• Lattice theory: local state can be modeled by congruence lattices
• Semigroup theory: changes can be modeled by monoid actions

The importance of lattice theory is that it allows us to model local behaviour. In geometry, the lattice of open sets of a topological space is used to model the local structure of space. By the use of sheaf theroy, structures are restricted to their local components. By the same token, the lattice of action congruences allows us to model the effect of local computations.

Models of state:
A local computation changes a region of memory, based only upon what is in that region in memory. It recieves no external inputs and it produces no external outputs. Such a local computation can be treated as a local action on memory. It then produces a homomorphism to its local quotient action.

The universality of computation means that no region in memory is treated any differently then any other. Computation can therefore be localized to any region in memory. Different regions in memory can have the same local actions, as they can have isomorphic quotients. In this way, the computations in different regions in memory can be compared algebraically.

• Action congruences: models of local memory
• Lens semigroups: models of local change

Action congruences can be used to describe any piece of information in memory. They both describe the subset of information that region contains, and they any local actions that operate on it. Lens semigroups are specific semigroup actions determined from the lattice of action congruences, by determining the actions that only effect on a given region in memory and not any other.

In general, memory comes equipped with a partition into a set of locations. By this sort of construction, we can get a boolean algebra of action congruences and lens semigroups. A computation may then partition this boolean algebra into regions that it effects locally. The composition of such partitioned computations produces a new partition no greater then the join of the two in the partition lattice.

Models of change:
We can use monoid actions to model the changes that occur to memory over time. Changes to state pile up over time in a manner that is compositional. It follows that monoid actions are models of change over time. In typical models like finite state machines and automata, there is a set of states with an associated transition function which defines how states change over time. Transition functions correspond to monoid actions.

Within the monoid action perspective, we can define a local action by a lens semigroup. Every lens semigroup is equipped with a homomorphism from the lens semigroup to the full transformation monoid. This homomorphism transforms a local action into a global one. By these homomorphisms, we can create an algebraic model of local state and change.