[OFFTOPIC] Time varying FSMs

[Omer Zak]

Of course, anything more complicated than a non-programmable calculator
can be considered to be a Turing machine (sometimes, with bounded memory
capacity).

However, it would be as useful as saying that every computer program is
a function transforming an input (such as a series of events in a GUI
based program) into an output (such as a series of screen behaviors).  

Therefore, as software developers, we use other concepts, which help us
to accomplish more.

I would like to propose another point of view.  Call it another series
of concepts, which may be more helpful than the concepts of a Turing
machine or a time-varying FSM.

Let's consider not a big time-varying FSM but time-varying cellular
automata.  Perhaps they won't vary their states and transition rules.
But they would vary their interconnections.  Those interconnections
would be as complicated and entangled, topology-wise, as those of
physical neurons.

It would be interesting to figure out interesting rules by which such
cellular automata would form new connections, break off old connections,
spawn new units, etc.

--- Omer


On Fri, 2015-01-30 at 10:51 +0200, Oleg Goldshmidt wrote:
> 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...
>  

-- 
No actual electrons, animals or children were harmed by writing this
E-mail message.
My own blog is at http://www.zak.co.il/tddpirate/

My opinions, as expressed in this E-mail message, are mine alone.
They do not represent the official policy of any organization with which
I may be affiliated in any way.
WARNING TO SPAMMERS:  at http://www.zak.co.il/spamwarning.html