<p>Let your original state machine $M(k)$ have $n$ states and transition relation $t(s,s&#39;)$, where each transition $t(s,s&#39;)$ updates the global variables $x_1,...,x_k$ by applying function 
$(x&#39;_1,...,x&#39;_k) = f_{t(s,s&#39;)} (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&#39;$</p>

<p>$t&#39;( (s,x_1,...,x_k), (s&#39;,x&#39;_1,...,x&#39;_k)) \Leftrightarrow t(s,s&#39;) \wedge [(x&#39;_1,...,x&#39;_k) = f_{t(s,s&#39;)} (x_1,...,x_k)]$.</p>

CC BY-SA 3.0
2011-12-21T11:13:29.410Z
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
CC BY-SA 3.0
2011-12-21T13:25:53.523Z
@Sylvain: right, thanks! fixed!
Martin Schwarz
CC BY-SA 3.0
2011-12-21T05:39:46.540Z
2011-12-21T13:27:55.437Z
2011-12-21T13:27:55.437Z
Martin Schwarz
<p>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.</p>

<p>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.</p>

<p>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).</p>

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

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

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

CC BY-SA 3.0
2011-12-21T00:15:01.650Z
Without the range constraint, this is trivially equivalent to Counter machines, which are Turing complete for k > 1.
rmmh
CC BY-SA 3.0
2011-12-21T11:17:23.273Z
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
CC BY-SA 3.0
2011-12-21T16:20:07.933Z
@B. VB.: you can accept the answer by checking the check mark next to it.
Martin Schwarz
CC BY-SA 3.0
2012-01-01T16:29:36.830Z
A (finite) set of unbounded variables is not "finite memory" at all.
Raphael
<fl.formal-languages><computability><regular-language><finite-model-theory><church-turing-thesis>
FSMs with finite memory
B. VB.
# FSMs with finite memory

(Asked by: username_0 on 2011-12-20)

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!

**Tags:** fl.formal-languages, computability, regular-language, finite-model-theory, church-turing-thesis

> **Comments:**
> **username_1**: Without the range constraint, this is trivially equivalent to Counter machines, which are Turing complete for k > 1.  
> **username_2**: I agree with username_1 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.  
> **username_3**: @username_0: you can accept the answer by checking the check mark next to it.  
> **username_4**: A (finite) set of unbounded variables is not "finite memory" at all.  

---

## 1 answers

### Answer by username_3 on 2011-12-21. Score: 5

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

> **Comments:**
> **username_2**: 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$.  
> **username_3**: @username_2: right, thanks! fixed!  

---

