the terrible effect of Krohn-Rhodes

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] langle y, x_1 dots x_{n-1}rangle

langle x_1, x_2 ... x_n rangle mapsto[pop] langle x_2 dots x_{n},nullrangle

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.

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s