Consider an FSM and a finite set of variables. The FSM has the special property that each state contains a set of commands, with each command taking the form of "variable = expr(variable, ...)" e.g., x = y + z + 2. The commands are "activated" whenever the FSM transitions into the containing state.

My question is what class of problems are computable in this model? Perhaps more specifically, say M(k) is one of these state machines with k variables.

Perhaps the only claim that seems obvious to me about this construction is that all computable problems for M(k+1) is strictly larger than for M(k).

Please pardon me if my question is not well formed, or if I'm misusing some terminology. Thanks in advance.

Edit: Suppose also we add the additional constraint that each 'variable' has some range [-r, r].

Edit2: Thanks Martin Schwartz. I don't have the "street cred" yet to upvote or respond to your answer. Thanks!

  • 1
    $\begingroup$ Without the range constraint, this is trivially equivalent to Counter machines, which are Turing complete for k > 1. $\endgroup$
    – rmmh
    Dec 21, 2011 at 0:15
  • 2
    $\begingroup$ I agree with rmmh if we assume that the variables range over the integers and that the transition functions can be partial (or some form of guards are allowed, like $x>0$), which is not explicitly stated. There is actually a wide range of answers depending on the exact definition of what the machines can do---so please be more specific! The most likely expected answer (given the title) in that of Martin Schwartz. $\endgroup$
    – Sylvain
    Dec 21, 2011 at 11:17
  • 1
    $\begingroup$ @B. VB.: you can accept the answer by checking the check mark next to it. $\endgroup$ Dec 21, 2011 at 16:20
  • $\begingroup$ A (finite) set of unbounded variables is not "finite memory" at all. $\endgroup$
    – Raphael
    Jan 1, 2012 at 16:29

1 Answer 1


Let your original state machine $M(k)$ have $n$ states and transition relation $t(s,s')$, where each transition $t(s,s')$ updates the global variables $x_1,...,x_k$ by applying function $(x'_1,...,x'_k) = f_{t(s,s')} (x_1,...,x_k)$. Then $M(k)$ is equivalent to a standard FSM with $n(2r+1)^k$ states, where each state encodes a tuple $(s,x_1,...,x_k)$ with each $x_i$ encoding one fixed value in $[-r,r]$, and new transition relation $t'$

$t'( (s,x_1,...,x_k), (s',x'_1,...,x'_k)) \Leftrightarrow t(s,s') \wedge [(x'_1,...,x'_k) = f_{t(s,s')} (x_1,...,x_k)]$.

  • 1
    $\begingroup$ The update function should be associated to the transition and not the state; the state space should be $Q\times [-r,r]^k$ (assuming the variables range over the integers), of cardinal $n(2r+1)^k$. $\endgroup$
    – Sylvain
    Dec 21, 2011 at 11:13
  • $\begingroup$ @Sylvain: right, thanks! fixed! $\endgroup$ Dec 21, 2011 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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