Re: [OFFTOPIC] Time varying FSMs
Shachar Shemesh writes: > Didn't you just describe a Turing machine? I don't think so. No one said anything about having an infinite number of states, for instance. There may or may not be a connection, so what? A Turing machine is a theoretical construct, I thought the question was about practical approaches to a problem. I don't even think the original question has a connection to a Turing machine. All Omer asked (as far as I understood) was how one would create a *finite* state machine that could "grow" or "lose" a state at runtime. I just thought of a typical FSM design where you specify the events the states, and the transitions/reactions, and in the end you have a "machine" class with a bunch of possible states one of which is current, and transition/reaction methods accepting events as arguments that do something and modify the current state. Even in the fanciest designs I've seen so far the components of the design are statically defined: you know all the states, events, and transitions at compile time, if you wish (my experience has been mostly in C++, guilty). This is why I thought of MOP that allows your program's objects to modify other objects and themselves at runtime, and modify your class hierarchy at runtime, too, since that is also an object. My intuition tells me that this will allow you to take the typical FSM design and start adding/removing/modifying states and transitions on the fly. If I have accidentally stumbled upon a way to construct a Turing machine, I don't know. I doubt it, at least because nothing has been said about expanding memory indefinitely. But I have not thought about it enough. -- Oleg Goldshmidt | p...@goldshmidt.org ___ Linux-il mailing list Linux-il@cs.huji.ac.il http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il
Re: [OFFTOPIC] Time varying FSMs
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. 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) must be describable given a combination of the initial states and the input. This is, precisely, how a Turing machine works. Shachar ___ Linux-il mailing list Linux-il@cs.huji.ac.il http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il
Re: [OFFTOPIC] Time varying FSMs
On Thu, Jan 29, 2015 at 10:21 AM, Shachar Shemesh wrote: > On 28/01/15 20:04, Oleg Goldshmidt wrote: > > Omer Zak writes: > > > After a brief Google search: > Does anyone know about any research, theory or practice of time-varying > finite state machines? > > Short answer: I don't. ;-) I'll offer a couple of thoughts, anyway. > > > I mean FSMs which might grow a new state, remove a state, add/subtract > transitions by means of meta-rules. > > I suppose it may be possible to write a FSM in such a way that > adding/removing the allowed states and transitions dynamically would be > possible. This would not be enough, though: any "interesting" FSM would > not just formally move from one state to another but do custom stuff as > a part of a transition, and one would want to create and load such > custom code dynamically. > > > 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. -- Ori Idan > > Shachar > > ___ > Linux-il mailing list > Linux-il@cs.huji.ac.il > http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il > > ___ Linux-il mailing list Linux-il@cs.huji.ac.il http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il
Re: [OFFTOPIC] Time varying FSMs
On 28/01/15 20:04, Oleg Goldshmidt wrote: > Omer Zak writes: > >> After a brief Google search: >> Does anyone know about any research, theory or practice of time-varying >> finite state machines? > Short answer: I don't. ;-) I'll offer a couple of thoughts, anyway. > >> I mean FSMs which might grow a new state, remove a state, add/subtract >> transitions by means of meta-rules. > I suppose it may be possible to write a FSM in such a way that > adding/removing the allowed states and transitions dynamically would be > possible. This would not be enough, though: any "interesting" FSM would > not just formally move from one state to another but do custom stuff as > a part of a transition, and one would want to create and load such > custom code dynamically. > Didn't you just describe a Turing machine? Shachar ___ Linux-il mailing list Linux-il@cs.huji.ac.il http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il