<p>No it is not universal, because it could be simulated by a 1-counter machine (with the jump-if-zero instruction) that stores the difference of the two counters  and an additional state (or program section)  that keeps track if the difference is positive or negative. But a 1-counter machine is not universal.</p>

CC BY-SA 4.0
2021-08-15T17:14:13.053Z
How do you simulate the dec instruction (which is really “if $a>0$ then $a:=a-1$” as the counter cannot become negative)? If you only keep track of the difference, you cannot tell when one of the simulated counters becomes $0$.
Emil Jeřábek
CC BY-SA 4.0
2021-08-15T20:05:03.123Z
@EmilJeřábek: good point. I'll check if other decidability resuts about counter machine variants can be used.
Marzio De Biasi
CC BY-SA 4.0
2021-08-15T16:31:13.647Z
2021-08-15T16:31:13.647Z
Marzio De Biasi
<p>I would like to show that the halting problem for some variant of two counter machine (Minsky machine) is undecidable:</p>
<p>instead of &quot;if c=0 goto i else goto j&quot;, there are &quot;if c&gt;d goto i else goto j&quot; commands (where c,d are the two counters). The inc\dec\goto\halt commands remain the same.</p>
<p>It is not hard to show that this problem is undecidable with 3 counters (for example, given an instance of the original problem, adding a third counter e that always equals 0, and we have that c!=0 iff c&gt;e, d!=0 iff d&gt;e).
My question is - is this variant known to be undecidable, with only two counters?</p>

<computability>
A variant of two-counter machine
Naama Shamash Hal
# A variant of two-counter machine

(Asked by: username_0 on 2021-08-15)

I would like to show that the halting problem for some variant of two counter machine (Minsky machine) is undecidable:

instead of "if c=0 goto i else goto j", there are "if c>d goto i else goto j" commands (where c,d are the two counters). The inc\dec\goto\halt commands remain the same.

It is not hard to show that this problem is undecidable with 3 counters (for example, given an instance of the original problem, adding a third counter e that always equals 0, and we have that c!=0 iff c>e, d!=0 iff d>e).
My question is - is this variant known to be undecidable, with only two counters?

**Tags:** computability

---

## 1 answers

### Answer by username_1 on 2021-08-15. Score: 3 | Accepted answer

No it is not universal, because it could be simulated by a 1-counter machine (with the jump-if-zero instruction) that stores the difference of the two counters and an additional state (or program section) that keeps track if the difference is positive or negative. But a 1-counter machine is not universal.

> **Comments:**
> **username_2**: How do you simulate the dec instruction (which is really “if $a>0$ then $a:=a-1$” as the counter cannot become negative)? If you only keep track of the difference, you cannot tell when one of the simulated counters becomes $0$.  
> **username_1**: @EmilJeřábek: good point. I'll check if other decidability resuts about counter machine variants can be used.  

---

