« Home

Menu

List of Publications
Blog
Problems that haunt me

Definition Mealy machine [lcc-0013]

April 4, 2024
Eigil Fjeldgren Rischel

A Mealy machine with input $A$ , output $B$ and state space $S$ , is a function $A \times S \to B \times S$ .

Context

Moore and Mealy machines in CST [lcc-0012]

April 4, 2024
Eigil Fjeldgren Rischel

Recall the classic definitions:

Definition Mealy machine [lcc-0013]

April 4, 2024
Eigil Fjeldgren Rischel

A Mealy machine with input $A$ , output $B$ and state space $S$ , is a function $A \times S \to B \times S$ .

Definition Moore machine [lcc-0014]

April 4, 2024
Eigil Fjeldgren Rischel

A Moore machine with input $A$ , output $B$ and state space $S$ , is a pair of functions $S \to B$ , $A \times S \to S$

The dynamical systems considered in Categorical Systems Theory are Moore-type machines - the output depends on the present state, but not (directly) on the input.

However, we can actually account for Mealy machines as well - a mealy machine with interface $A$ (which is now an arena, i.e a pair of sets in the simplest case) and state space $S$ is a lens $TS \otimes A \to I$ , where $I$ is the monoidal unit (here we assume the dynamical systems doctrine has enough structure to make the category of lenses monoidal).

In the simplest case, arenas are pairs of sets - then we have a lens $\binom {S \times A'}{S \times A} \to \binom {*}{*}$ , which amounts to a map $S \times A \to S \times A'$ as desired. But note that the input/output pairing has changed - now $A'$ is the output and $A$ the input

Given a Mealy machine and a Moore machine with the same interface, we can pair them to obtain a closed dynamical system $T(S \otimes S') \to I$ . In general we can plug the two types of machines into each others' interfaces
Mealy machines reindex along lenses, but in the opposite direction from Moore machines
Given Mealy machines $TS \otimes A \to I$ and $TS' \otimes A' \to I$ , and a chart $A \rightrightarrows A'$ , there is a set of "maps of systems over this chart", namely maps $S \to S'$ and 2-cells filling the resulting square. Thus we get something very similar to the usual double category of systems, lenses and charts, but with the lenses working in the opposite direction from what they usually do