Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
Without the range constraint, this is trivially equivalent to Counter machines, which are Turing complete for k > 1. – rmmh Dec 21 '11 at 0:15
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. – Sylvain Dec 21 '11 at 11:17
@B. VB.: you can accept the answer by checking the check mark next to it. – Martin Schwarz Dec 21 '11 at 16:20
A (finite) set of unbounded variables is not "finite memory" at all. – Raphael Jan 1 '12 at 16:29

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)]$.

share|cite|improve this answer
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$. – Sylvain Dec 21 '11 at 11:13
@Sylvain: right, thanks! fixed! – Martin Schwarz Dec 21 '11 at 13:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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