Vladimir Z. Nuri wrote:
>
> Nico: thanks very much for the explanation. your information
> about why you are pursuing the FSM decomposition approach
> makes a lot of sense to me now (of the part I understand),
> because I've debugged a lot
> of hardware and software in my life, and a system that
> minimizes debugging complexity is very useful.

It's not only testing that benefits from FSM structure, but
especially the "coupling" between components is minimized by
cascade decomposition. In fact, this relation between "preserved
state partitions" and machine structure was analysed and put
forward in the book of Hartmanis/Stearns: "Algebraic struture
of Sequential Machines" (McGraw-Hill (?), Englewood Cliffs 1970?)
Unfortumately it is out of print. It stays at the state-level
though, and when I in the early seventies was looking for a way
to order FSM's I read the book in our Lab library, and got the
shock of my life (I remember precisely the moment & enviroment)
when i the last chapter I saw a remark, going like: "Oh, and then
of course there is the semigroup of an FSM", but they did not do
anything with it! The "sequential closure" (=semigroup) does
away with the two separate sets: input-alphabet A, and internal
state set Q, and _integrates_ them (as it were) into _one_ set S,
that is closed undet concatenation of input strings in A*.

Very strange concept that is: the input(strings) *and* states are
_both_ in semigroup S(), which is a closed collection of functions
in A*: S --> S, while somehow Q *also* has merged into S as stateset!
How can this be, that each element of S is _both_ an argument of a
function (as state) and also function itself (as transforming S --> S).

The answers is; sequencing bring asymmetry into the picture, and
two functions a: S-->S and b: S-->S can be composed into ab: S-->S
which is defined by its transitions: q(ab) = (qa)b for all q in S.

Notice that seimgroup S() of all distinct Q-transforms in A* is itself,
re-interpreting its composition table S x S --> S, *also* a state
machine M(S,S) where each element of inputset S maps stateset S into
itself, so M(S,S): S x S --> S, which (by isomorphism definition)
has the same "structure as M(Q,A): Q x A --> Q.

Remember the definition of equivalent machines?
They have isomorphic closures (semigroups).

It does take a while (it took me years) to see this simple truth,
that (non-commutative) sequencing is in fact modelled by our concept
of "time" -- and in semigroups is represented by going left-to-right
in seq_composition q(ab) = (qa)b for all q in Q and a,b in A*.

Actually, Clifford/Preston (1961) "Algebraic Theory of Semigroups"
(two volumes!), my "bible", introduces the left-to-right notation
for function composition. This is *much* more instructive then the
usual f(g(x)) notation, which now becomes: x(fg) = (xf)g, so reading
from left to right: take argument x, then apply function f, and on
the result xf apply function g, to get result (xf)g in the codomain,
which is the same result as applying composed function 'fg' to
argument x, for all x in the domian.

Now for closed function compostion, without restriction
("context free"): domain = codomain (is stateset Q, or closure S).
You see ? ... It all becomes *so* extremely trivial, that you
just need quite a while to get used to such simplicity! You must
namely unlearn all those complex things & nasty notations that you
were taught at early age. My advantage was actually that I'm not a
mathematician, and had very little 'luggage' to cast off;-). Just
inventing most of it myself, and later discovering that in some rare
books (Hartmanis/Stearns, Clifford/Preston) those concepts were
known, but not quite used & interpreted -- if you know what I mean.

> looking over your ideas makes me begin to wonder if there is
> a sort of naturual "decomposition" of Turing machines similar
> to your FSM approach. I wonder if your FSM decompositions
> are minimizing complexity in some kind of way that can
> be formalized. in other words, you take a large FSM, break
> it into smaller units, and in some sense you seem to be
> minimizing some kind of complexity of the larger FSM. this
> very much reminds me of structured programming with TMs,
> such that larger programs are broken into subroutines etc.

Precisely.

> nobody has ever found a way to "decompose" TMs into
> subcomponents starting from the TM itself, to my knowledge.
> it is easy to build up a TM from many subroutines, and the
> various researchers out there do this daily in the field
> of course, it is one of the most basic techniques. but I
> wonder if some kind of "decomposition" of TMs exists. if
> so, it would probably have very important theoretical
> properties.

In fact, for me "synthesis" should be the same as "analysis"
in the sense of "factoring the specification". The only problem
is that most specs in practice are *not* complete: not every
state has under *every* input a specified next-state (& output),
because in many states only a small subset of inputs is relevant
("in that context"). So most FSM specs are very "sparse", and
the art of design (synthesis) is to choose the 'best' filling
to get a fully specified machine (fill in the dont-cares), and
only *then* decompose = factorize. Uptill now I assumed a full
spec. Obtaining that from a sparse spec is the main problem,
really. That is rather the problem of "embedding" a sparse spec
FSM into a full-spec FSM1. And here the closure idea (semigroup)
is really indispensible & crucial, is my gut feeling.

> there are a lot of theorems that make studying
> TMs very difficult, that say for example there exists no
> "best" TM for a given problem because you can always
> optimize further. but this doesn't seem right to me.
> I suspect there is some property of TMs waiting to be
> discovered that is analogous to complexity that can
> in fact be minimized somehow, in a way that corresponds
> to intuitive notions about program complexity. as I
> program, I do believe there are "best" solutions for
> given problems, but the theory does not currently seem
> to support that notion.
>
> I am well acquainted with FSMs so most of your post
> makes a lot of sense to me. the semigroup stuff is starting
> to make sense with your last post, which is very helpful.
> I'll also check out the other paper you listed.
>
> I think you're definitely onto something very big, by
> relating semigroup properties in mathematics to computational
> structures. list members, take note! potentially fruitful
> mathematical research area!!

Thanks Vladimir, I feel a bit less lonely now (after 25 years
of plugging away) - trying to make people understand the essence
of associative Generators (=FSM) & Closures (=Sgrp):
<==> function compostion
<==> stringing boxes with input/state/output arrows together
<==> which we all do, in some sense, don't we ?-)

I admit, though, that this takes quite some "thinking-frame"
re-adjustment, and a fearless approach to these huge closures
(max |S| = q^q nota bene!). But the rewards, in terms of
concepts & understanding, are *also* huge, even more HUGE
(my gut feeling).

> this has been something I've been wondering
> about for a long time. I've bought a lot of group theory
> books but never could figure out a correspondence, although
> I was sure one probably existed!! you come along at a nice
> time to reveal it. also the idea that the 5 basic semigroups
> correspond to intuitive notions about memory and other
> basic components seems very deep to me.

They in fact are classified as:

1-generator. There are two types:
==========
C2: Periodic counter <--> ADD mod 2 (or Cn: mod n, in general)

U2: Monotone counter <--> MPY mod p^n contains max chain n (Un)
('U' = uni-versal = one-way: "convergence", with a final state)

2-generators
============ Necessarily idempotent aa=a, bb=b, otherwise a*
and/or b* would be a proper subclosure!) There are two types:

H2: Commuting idt's aa=a, bb=b, ab=ba --> necessarily orderable
(an ordering relation is transitive, anti-symmtric, reflexive;
and notation a >= b means: ab=ba=b : a is unity for b).
This is the Boolean AND cq OR (isomorphic!), or MPY mod 2.
'H' comes from "hierarchy", that is: ordering.

Non-commuting, of which there are (again) two types:
>>>>>>>.<<<<<<
L2: Left-copy sgrp: ab=a for all a,b in S() --> branch
(the first input determines the next-state, which never
changes anymore... very strange "machine", but *that*
is what you expect from a dicision, dont you?)

R2: Right-copy sgrp: ab=b for all a,b in S() --> set/reset FF
(the last input determines the next state, every time;
the short-term memory of a binary FlipFlop)

All these 5 types of sequential behaviour can of course be
generalized from 2 states to n states! In a (coupled) network
they are conjectured to model *every* FSM (sequential behaviour):
5 basic types of seq.machines: {Cn, Un, Hn, Ln, Rn}
Dimension: 1 1 2 2 2 (# generators)
Has ideal: n y y n n (viz: "zero")
Commuting: y y y n n ( ab = ba )
Idempotent: n n y y y ( aa = a )

> I'll be looking over your papers, thanks again for the posts.

You're welcome, the pleasure is all mine!
--
Ciao, Nico Benschop. | AHA: one is Always Halfway Anyway
http://www.iae.nl/users/benschop | xxxxxxxxxxxxxxxx.xxxxxxxxxxxxxxxx

____________________________________________________________________

List Site: http://www.findmail.com/list/theory-edge/
To unsubscribe, send to theory-edge-unsubscribe@...

FREE group e-mail lists at http://www.findmail.com