BTW, caveat: the gsm_superset program written in Perl
mentioned in my post is not debugged very well. the general
idea and structure of the code is correct,
I do believe it can be used to resolve whether some
TMs halt in theory. but I abandoned the code when I realized it
probably couldn't solve the 3n+1 problem. I don't
recommend spending too much time with this code.

however, "iterative exclusion" is an interesting
technique I got to work to resolve some primitive
TM-like computations as either halting or nonhalting.
more information at

http://www8.pair.com/mnajtiv/halt/iterative.html

the code gsm_superset.csh is definitely heavily
tested and gives interesting results described on
this page.

I believe all this is some smaller element of a much
larger theory that I am pursuing intermittently.
there are some odds-and-ends ideas here.

(another caveat: I've noticed some minor incompatibilities
between perl 4 and perl 5 with the code all written in
perl 4. I've never gone back to port the code to perl 5.)

I can see if I'm going to talk to Nico in his own language
I'm going to have to study a lot of my group theory
books!! be patient Nico!! meantime maybe someone here
who knows about group theory can engage in this discussion..
I'm surprised no one else is saying much.

in my last post I talked about Mealy machines. a mealy
machine is a FSM with an output associated with each
input transition. in other words, for an input '0', the
transition function may be (s2,1) where s2 is the next
state and '1' is the output.

the paper talks more about "generalized sequential machines".
this is a machine that allows transitions with an
input string, an output string, and (as I recall) possibly
even nondeterminism. a GSM can be simulated with a mealy
machine that expands out all the strings with extra states,
one state per character in the input and output strings.

Nico, regarding decomposition, this is what you said:

>I want a 'balanced' decomposition into
>a "least-coupled" network of smaller state
>machines, preferably in a cascaded
>fashion (eg. for testing purposes;-) --
>But if not possible, then a
>"cyclic-coupling" pattern possibly (as
>necessary for a simple-group machine: a
>prime machine!).

I think you're on to something here, and I continue to
wonder if this same framework could be used to analyze TMs.
you say you are not too fond of TMs, but you realize FSMs
are not computationally very powerful!! of course if we
can figure out how to convert the GSMs I have been studying
into FSMs you can study..

if you could more formally define this requirement above,
I think it would help. define "balanced", "least
coupled", "cyclic coupling" etc. using mathematical terms.
at your leisure!!



____________________________________________________________________

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