One of the most interesting theorems in computer science is the Krohn-Rhodes theorem that shows a strong link between basic computer science and group theory. Crudely, the KR theorem extends Jordan-Holder \( (H_1 \triangleleft H_2 … \triangleleft H_n=G)\) to state machines, but it does it in a way that doesn’t get us very far in understanding the structure of state machines. The problem is that the “division” is too restrictive. In terms of state machines, KR requires us to turn \( M\) into \( M_1 \rightarrow M_2\) where the input of \(M_2\) depends only on the system input and the output of \(M_1\). This is called a “loop free” decomposition and Hartmanis-Stearns worked on it before KR teased out the underlying math. You can build a ripple carry adder that way and it makes sense that the simple devices that concerned early CS researchers seemed amenable to such a decomposition, but a few steps down the path and we come to systems that do not want to be decomposed into loop-free series at all. Consider a queue – when a new element is inserted each element needs the output of its neighbor to the back to get its new value – very nicely loop free. But consider a stack. A push makes each element take an input from its neighbor to the right and a pop makes each element take an input from its neighbor to the left.
\[ \langle x_1, x_2 … x_n \rangle \mapsto[push\ y]\mapsto \langle y, x_1 \dots x_{n-1}\rangle \]
\[ \langle x_1, x_2 … x_n \rangle \mapsto[pop]\mapsto \langle x_2 \dots x_{n},null\rangle \]
In fact the stack is serially loop free – it has a nice loop free ordering per operation – but Krohn-Rhodes doesn’t go there (you could get to loop free by adding a counter to each element). Anyways, the result is a theory that bounces off the observed or designed structure of computational objects and, at least to me, that designed structure is the interesting structure.