0
$\begingroup$

Consider a universal $\{0,1\}$-$k$-counter machine where each of the $k$ registers has a value in $\{0,1\}$ (as opposed to any non-negative integer in the usual formulation), and there are states $q_1, .., q_f$ with $q_1$ initial and $q_f$ final. The set of instructions are chosen from the following: increment $q_a {+}r_j q_b$ i.e. when in state $q_a$ increment register $r_j$ from $0$ to $1$ and transition to state $q_b$, decrement $q_a {-}r_j q_b$ i.e. similar to before but from $1$ to $0$, and forking from $<q_a; n_1, .., n_k>$ to $<q_b; n_1, .., n_k>$ and $<q_c; n_1, .., n_k>$.

The machine is non-deterministic in the sense that more than one instruction may be applicable to a configuration, and universal because a configuration is accepted iff every branch in the computation tree leads to $<q_f; 0, .., 0>$.

i) What is the name for such a CM ? (surely this machine, or an equivalent formulation, must have been studied..)

ii) What is the complexity lower bound for determining if there is a computation from a given configuration $<q_i; n_1, .., n_k>$ such that every leaf in the computation tree is $<q_f; 0, .., 0>$ ?

EDIT Given a universal $\{0,1\}$-$k$-counter machine C (as per description in question) we can decide if it accepts $w \in \{0,1\}^k$ using a TM that accepts input $<C,w>=n$ in $2^{O(n)}$ time by generating all computation trees of height $1,2, .., 2^k$ ($\leq 2^n$). Thus acceptance can be decided in EXPTIME. What is lacking is the lower bound.

Added MathJax equations

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Is $k$ fixed? If yes, then the model should be equivalent to a simple NFA $\endgroup$
    – Marzio De Biasi
    Sep 13, 2021 at 11:19
  • $\begingroup$ The definition of the machine is incomplete. You tell us what the set of allowable instructions is, but how is the set of applicable instructions for a particular configuration chosen? What does it depend on? Please give a complete mathematical definition of the semantics of this machine. $\endgroup$
    – D.W.
    Sep 13, 2021 at 20:49
  • $\begingroup$ @Marzio, for any given machine, the k is fixed. I don't see the encoding you have in mind. For example, how would the NFA would account for the universal property where the configuration is accepted if all the children in the computation tree accept. $\endgroup$
    – RRRR
    Sep 14, 2021 at 5:04
  • $\begingroup$ @D.W. What I described is the definition of the abstract machine. A concrete machine is obtained by choosing (however you wish) some subset of applicable instructions. This is similar to how there is an abstract definition of a Turing machine, and a concrete TM is obtained by choosing a concrete set of states, transition function etc. $\endgroup$
    – RRRR
    Sep 14, 2021 at 5:14

1 Answer 1

Reset to default
2
$\begingroup$

As Marzio De Biasi states, since $k$ is fixed, this is equivalent to a NFA. To deal with the "universal" requirement, use the subset construction to convert to a DFA.

In particular: the state of the DFA is the set of configurations of the counter machine that can be reached after reading the input so far. Since $k$ is fixed, there are only finitely many possible configurations of the counter machine, so only finitely many sets, so only finitely many states of the DFA. The accepting state of the DFA is the singleton set containing $\langle q_f;0,\dots,0\rangle$.

Improve this answer
$\endgroup$

Your Answer

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

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