World's most popular travel blog for travel bloggers.

FSM + state data is Turing complete abstraction?

, , No Comments
Problem Detail: 

I'm playing with Akka FSM. The declaration of a an Akka FSM consists of states + data mantained during the states (the akka doc is more clear than me) + events that trigger transitions between states. Can we say that such a formalism is Turing-complete? I can't think of a problem that can't be solved this way.

Asked By : tmnd91
Answered By : Thomas Klimpel

Maybe your questions should be more self-contained, but let's assume that your description together with the documentation from Akka amounts to the following description:

  • The input consists of events, and the output consists of actions.
  • Even so output actions may trigger further input events, this relation is neither fully deterministic, nor part of the machine model itself.
  • There are a finite number of states that determine which rules will be applied to the input event and the internally stored data, for determining the output action, the new state, and the modification of the internal data.
  • After an output action is performed, the machine transitions into a new state, and waits for further input events.

Under these conditions, the machine model is only Turing complete if already the rules for determining the output action, the new state, and the modification of the internal data were Turing complete.

What you have in mind is probably some mechanism for triggering input events as part of the output action. So the FSM is supposed to have some sort of first-in, first-out event queue, and the output action can post input events to this queue. In this case, this machine model would be more powerful than a queue automation, which is known to be Turing complete.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43582

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback