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.

  • 2
    $\begingroup$ Welcome to SE Computer Science. This site is not about specific systems. So, to be on topic, this has to be described as an abstract problem. I think you should provide a self contained description of the problem, since readers cannot be expected to go read the Akka doc. $\endgroup$ – babou Jun 14 '15 at 18:57

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.