Vladimir Z. Nuri wrote:
>
> Nico, I understand fairly well now what you are doing
> with the FSMs. the group theory is still a little
> out of my reach, but the composition of FSMs is something
> I'm very familiar with.
>
> I just asked you if your results could be extended to TMs somehow.
> I think I may have something close to a solution here.
>
> on my web site is a paper I wrote on modelling a TM computation
> as a sequence of computations of Mealy machines.
>
> http://www8.pair.com/mnajtiv/halt/super.txt
>
> the paper has some glitches, but the general ideas are there.
>
> I suspect it can be shown that Mealy
> machines can be equivalent to the cases you are
> considering in which the state of a machine is input
> to the next. for the Mealy machines, each input transition
> has a corresponding output symbol. Hopcroft and Ullman
> have a lot of proofs showing the equivalence of Moore
> machines, Mealy machines, FSMs, etc. I haven't worked
> out an exact proof, but your machines are clearly
> equivalent somehow. maybe just a Mealy machine in which
> the output symbol equals the state symbol?
> personally I find Mealy machines much more intuitively
> appealing, because they have an input/output concept.
>
> you might consider recasting your results in terms
> of compositions of Mealy machines. the composition
> of FSMs is not all that recognized in the literature,
> but there is a very natural way to do compositions
> of Mealy machines which I describe in the paper.
> if you want to do a composition of a function, this
> is normally done in terms of an "input" and an
> "output". the FSM has only "input" whereas the Mealy
> machine has output.

I copied your text on gsm_supersets and will get back to you.

Meanwhile: I always forget what's Moore and what's Mealy,
so I use a "donkey_bridge": --- Moore is less than Mealy ---
meaning that Moore has no output function, and Mealy does;-)

Now notice in my short expose' that I started with an FSM
(that is: no output function), but in decomposing it, via a
preserved state partition, into a cascade of two smaller FSM's
(leading ==> trailing machine: M1 ==> M2) the coupling function
"came about" somehow from self. This is taken care of by the
state congruence, as it were: there is no choice. In fact,
while closure S1 = A1*/Q1 of M1 is a "factor" or "image" of
the whole initial S=A*/Q, we can take closure S2 of M2 to be
a sub-semigroup of S (orthogonal to image S1). The rest
-- coupling function -- follows. So you see: we have a
Mealy machine after all, that is M1 with output function.
Usually the initial spec *also* has an output function (hence
is a Mealy machine), but that is Boolean stuff: combinational,
that can be "split-off" for synthesis purposes.
The sequential state coding (= decomposition into smaller
"parallel" components, down to binary) steers the combinational
coding later on.

> one question I have. you seem to have said no one has
> figured out a way to decompose arbitrary FSMs into the basic
> building blocks. if you could state formally the question
> you want answered, it would help. what is the key thing
> that hasn't been discovered? it seems to me that the
> mathematicians have been decomposing groups into the
> fundamental ones for so long, I presume there is a huge
> theory surrounding this. isn't there a basic algorithm?

Sure, but don't confuse groups with semigroups! It is like
comparing conductors to semi-conductors (which latter are
*much* more useful for elctronics in general). Actually,
groups are a special kind of semigroups (with permutations,
instaed of general transformations of the state set).

Of course, finite groups are "well known", as in the
Krohn/Rhodes automaton decomposition theory from the sixties
(not much happened since), but upto a point. Namely: their
components are "prime machines" with "simple-group" closure.
This means: HUGE permutation groups (the smallest is A5 of
order 60, the even perm's of 5 states). Because their condition
is: cascade decomposition. And that is no surprise, since they
(without saying so) applied the known Jardan/Holder chain-
decomposition theorem (last century) to "solve" a finite group
into a cascade (chain) of prime (=simple_group) components!

Now such huge group machines G are NOT quite practical as
components for synthesis. So at least they *also* should be
decomposed, necessarily in a non-cascade fashion, say a cycle
of Basic Machines (Cp, prime periodic counters, which are
subgroups of G). Such concept of "decomposing a simple group"
is considered 'absurd' by most mathematicians (I checked!) --
it is like factoring a prime. However, a prime *can* be
decomposed, namely as a sum of terms (and that is why I call
a sub-semigroup an additive component, and an image-semigroup
a multiplicative component or divisor). A simple group G *does*
have plenty of subgroups, but not a single image group (by def'n)

> again I suspect that the parallels between group theory
> and computation are very important and have not been
> explored very significantly, and this may be one of the
> important ways that future mathematics and computation
> are unified into a more coherent and powerful theory.


Sure, the controller (program) of a Turing machine TM is I presume
finite, and in fact is a finite FSM (correct me if I am wrong).
But the TM does have an infinite tape, which can be employed to
extend the state-set to any size desired (potentially countable
infinite). That is why for all practical purposes (APP) I do
not like TM's, because this state-extention is highly artificial,
and mixes the actual TM function with stuff to extend its state-set.
Not a very practical way of going about synthesis, is it?

Again, I'll check your paper, and see if I can understand it.
For me the last I remember of TM's was a course in U-Waterloo,
Canada, in the late sixties (my PhD grad study there;-(

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