[OFFTOPIC] Time varying FSMs

[Oleg Goldshmidt]

Shachar Shemesh <shachar at shemesh.biz> writes:

> On 29/01/15 15:37, Ori Idan wrote:
>                 
>         Didn't you just describe a Turing machine?
>
>     Turing machine is finite and has certain number of states with
>     defined transitions. I think what Omer meant here was more of a
>     dynamic Turing machine.
>     
> Since a Turing machine has an infinite amount of memory, and since
> that memory can be used in order to decide on which transitions to
> perform, I disagree with your statement that there is a difference.

I think you are both right. A Turing machine has a finite and static
table of states and transitions, having infinite memory does not make
the number of allowed states infinite (cf. my negligent slip in a
previous post). 

> After all, each new state that Omer's "FSM" (I'm not sure how you can
> call it a Finite state machine, when you do not bound the number of
> states it has, hence the quotes) 

"Finite" != Constant, at least not in my mind. I have not checked
whether the definition of FSM includes a constant number of states. In
any case, it's semantics, let's call it a D(ynamic)SM. 

> must be describable given a combination of the initial states and the
> input. This is, precisely, how a Turing machine works.

And here you may be right. The "must be describable" bit requires a
proof, but the proof may be simple, given that "input" is arbitrary (as
far as I can see) and may be infinite. I am with you, so I am willing to
give it some more thought.

How about modelling something evolving? Assume you can model me, in
sufficient detail, as a state machine. Intuitively[*], I am a bit more
complex and have a richer state set than an amoeba. It may be
theoretically possible to model the evolution from an amoeba all the way
to a primate based on a static set of elementary particles and their
states, and infinite memory (rings a bell?). That model might not be
practical, exactly for this last reason.

In my mind it's a question of modelling and representation. We all know
how to create abstractions, modularize, etc. So if we have a module that
is, for all intents and purposes, an FSM, can we create an event (and
events can carry data, and programs are data, and metaprograms doubly
so) that will deliver a metaprogram that will be executed as a part of
the reactor and will add another state and some new transitions to the
FSM? After that, our module will have new capabilities (it will have
"learnt" something new, if you will).

Can this be described as a larger system that includes both the FSM in
the previous paragraph and stuff external to it (including our
metaprogram that the FSM knew nothng about until it arrived)?
Probably. And that larger system may be a regular FSM with a very large
state set / transition table. However, it may be so large that it will
be impractical (will probably become unmaintanable even earlier - that's
why we modularize, eh?). And all the new states/transitions might not be
known at "compile time".

In conclusion, it well may be that any system that include things that
can be modelled as our imaginary DSMs can be theoretically represented
as a Turing Machine. An implementation of such a Turing Machine may be
not practical, however, and therein lies a possible motivation for
exploring DSMs as a more practical approach.

[*] "Intuitively" here means that a negation of the statement will
    require a proof...
 
-- 
Oleg Goldshmidt | pub at goldshmidt.org