<p>I found a similar argument for context-free languages, which can be used here.
It is not decidable, since universality for non-deterministic reversal-bounded multicounter machines is undecidable, but becomes decidable for the deterministic version.</p>

<p>Suppose we can decide if $M$ can be determinized, and perform the determinization if it can.
Then we can decide if $L(M) = \Sigma^*$ as follows:</p>

<p>If $M$ cannot be determinized, then clearly it is not universal, since there is a deterministic machine accepting $\Sigma^*$.
If $M$ can be determinized, then we determinize it and test if it is universal.</p>

<p><a href="https://cs.stackexchange.com/questions/1972/decide-whether-a-context-free-languages-can-be-accepted-by-a-deterministic-pushd">This question</a> on CS.SE give the analogous argument for CFL vs. DCFL.</p>

CC BY-SA 3.0
2013-07-03T17:06:33.547Z
2013-07-03T17:06:33.547Z
2017-04-13T12:48:30.830Z
Joey Eremondi
<p>I'm wondering if anyone can point me to either an algorithm or an undecidability proof for the following question:</p>

<p>Given a non-deterministic reversal-bounded multicounter machine $M$,
is there some deterministic reversal-bounded multicounter machine $M'$
such that $L(M) = L(M')$?</p>

<p>For anyone interested, reversal-bounded counter machines are described at length
in <a href="http://dl.acm.org/citation.cfm?id=322058" rel="nofollow">Oscar Ibarra's Paper</a> about them.</p>

<reference-request><fl.formal-languages><computability><automata-theory><decidability>
Is it decidable whether the langauge accepted by a reversal-bounded counter machine is deterministic?
Joey Eremondi
# Is it decidable whether the langauge accepted by a reversal-bounded counter machine is deterministic?

(Asked by: username_0 on 2013-07-03)

I'm wondering if anyone can point me to either an algorithm or an undecidability proof for the following question:

Given a non-deterministic reversal-bounded multicounter machine $M$,
is there some deterministic reversal-bounded multicounter machine $M'$
such that $L(M) = L(M')$?

For anyone interested, reversal-bounded counter machines are described at length
in [Oscar Ibarra's Paper](http://dl.acm.org/citation.cfm?id=322058) about them.

**Tags:** reference-request, fl.formal-languages, computability, automata-theory, decidability


---

## 1 answers

### Answer by username_0 on 2013-07-03. Score: 2

I found a similar argument for context-free languages, which can be used here.
It is not decidable, since universality for non-deterministic reversal-bounded multicounter machines is undecidable, but becomes decidable for the deterministic version.

Suppose we can decide if $M$ can be determinized, and perform the determinization if it can.
Then we can decide if $L(M) = \Sigma^\*$ as follows:

If $M$ cannot be determinized, then clearly it is not universal, since there is a deterministic machine accepting $\Sigma^\*$.
If $M$ can be determinized, then we determinize it and test if it is universal.

[This question](https://cs.stackexchange.com/questions/1972/decide-whether-a-context-free-languages-can-be-accepted-by-a-deterministic-pushd) on CS.SE give the analogous argument for CFL vs. DCFL.


---

