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 <shac...@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 _______________________________________________ Linux-il mailing list Linux-il@cs.huji.ac.il http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il
