<p>The problem has been solved in: </p>

<p>Oscar H. Ibarra, Nicholas Q. Trân, A note on simple programs with two variables, Theoretical Computer Science, Volume 112, Issue 2, 10 May 1993, Pages 391-397, ISSN 0304-3975, <a href="http://dx.doi.org/10.1016/0304-3975%2893%2990028-R">http://dx.doi.org/10.1016/0304-3975(93)90028-R</a>.</p>

<p>Let $TV$ be the class of languages recognized by two-counter machines.</p>

<blockquote>
<b>Theorem 3.3</b>: For any fixed integer $k \geq 2$, $L_k = \{ n^k \mid n \geq 0 \} \notin TV$
</blockquote>

<p><br>Note: it's strange that in the Ibarra&amp;Tran's paper   </p>

<blockquote>
<b>Theorem 3.4</b> Let $f$ be a total function with infinite range and such that the relation $f(a + bn)=f(a)+cn$ for all $n \geq 0$ does not hold for any triple $(a,b,c)$; then $f$ cannot be computed by any two-counter machine.
</blockquote>

<p>is proved and the authors say that it has been derived in a slightly different form in:</p>

<p>I.M. Barzdin, Ob odnom klasse machin Turinga (machiny Minskogo), Russian, <em>Algebra i Logika</em> 1 (1963) 42-51</p>

<p>but don't cite Rich Schroeppel's paper (1972) in which the theorem is also derived ... :-)</p>

CC BY-SA 3.0
2014-03-02T14:27:00.720Z
I'm not sure that it's ever strange that a twenty-year-old paper doesn't get cited: presumably the authors didn't know about it and nor did the referees.
David Richerby
CC BY-SA 3.0
2014-03-02T23:51:32.517Z
@DavidRicherby: I would be curious to see how the theorem in Schroeppel (1972) differs from the corresponding one in Barzdin (1963) :-) ... but I don't have access to the Barzdin's paper
Marzio De Biasi
CC BY-SA 3.0
2014-02-22T12:20:38.087Z
2014-02-22T12:20:38.087Z
Marzio De Biasi
<p>Can a standard two counters ($c_1,c_2$) machine with the following instructions:</p>

<pre><code>1) ADD 1 to c_i, GOTO label_j
2) IF c_i = 0 GOTO label_j, OTHERWISE SUB 1 to c_i and GOTO label_k
3) GOTO label_j
4) HALT and ACCEPT|REJECT
</code></pre>

<p>decide the following language:</p>

<p>$$L = \{ n^2 \mid n \geq 1 \}$$</p>

<p>(the input is initially loaded in the counter $c_1$)?.</p>

<p>Is it still an open problem? (cf. Rich Schroeppel, "A Two counter Machine Cannot Calculate $2^N$" [1972])</p>

CC BY-SA 3.0
2014-02-15T21:11:53.997Z
I am trying to grasp the most important results of the paper and I am really surprised by the Arithmetic Progression Theorem on page 12. Suppose $F(N)$ is the largest odd divisor of $N$. Then what would $D$ and $M$ be? Probably I have misunderstood something somewhere...
domotorp
CC BY-SA 3.0
2014-02-15T21:18:54.023Z
Now I'll look at it, but are you sure that "the largest odd divisor of N" is computable by a 2CM?
Marzio De Biasi
CC BY-SA 3.0
2014-02-15T21:24:27.940Z
@domotorp: by the way I asked the same question also on [mathoverflow](http://mathoverflow.net/questions/157409/n2-and-two-counter-machines), but didn't get new ideas
Marzio De Biasi
CC BY-SA 3.0
2014-02-15T22:02:01.217Z
I think that if you keep on dividing N by 2 until you can, you will get the largest odd divisor and this should be straightforward to do.
domotorp
CC BY-SA 3.0
2014-02-15T23:19:46.380Z
Ok, I think that if $N = 2^k x$ (with $x$ odd) and $2^{i}$ is the largest power of two greater than $N$, $2^{l}$ is the largest power of two greater than $x$, we can set $D=2^{i-1}$, $M = 2^{l-1}$. Informally if $N$ has $i$ bits, then you can  safely expand the most significant bit of $N$ adding $j 2^{i-1}$ and the result will change by $j 2^{l-1}$.
Marzio De Biasi
CC BY-SA 3.0
2014-02-15T23:34:03.263Z
typo ... replace "largest power" with "smaller power" :)
Marzio De Biasi
CC BY-SA 3.0
2014-02-16T06:18:11.873Z
Oh I see, so D and M can depend on N! This way the statement is much more believable...
domotorp
<fl.formal-languages><counter-automata>
Can a two counters machine decide $n^2$?
Marzio De Biasi
# Can a two counters machine decide $n^2$?

(Asked by: username_0 on 2013-10-27)

Can a standard two counters ($c_1,c_2$) machine with the following instructions:
1) ADD 1 to c_i, GOTO label_j
2) IF c_i = 0 GOTO label_j, OTHERWISE SUB 1 to c_i and GOTO label_k
3) GOTO label_j
4) HALT and ACCEPT|REJECT

decide the following language:
$$L = \{ n^2 \mid n \geq 1 \}$$
(the input is initially loaded in the counter $c_1$)?.
Is it still an open problem? (cf. Rich Schroeppel, "A Two counter Machine Cannot Calculate $2^N$" [1972])

**Tags:** fl.formal-languages, counter-automata
> **Comments:**
> **username_1**: I am trying to grasp the most important results of the paper and I am really surprised by the Arithmetic Progression Theorem on page 12. Suppose $F(N)$ is the largest odd divisor of $N$. Then what would $D$ and $M$ be? Probably I have misunderstood something somewhere...  
> **username_0**: Now I'll look at it, but are you sure that "the largest odd divisor of N" is computable by a 2CM?  
> **username_0**: @domotorp: by the way I asked the same question also on [mathoverflow](http://mathoverflow.net/questions/157409/n2-and-two-counter-machines), but didn't get new ideas  
> **username_1**: I think that if you keep on dividing N by 2 until you can, you will get the largest odd divisor and this should be straightforward to do.  
> **username_0**: Ok, I think that if $N = 2^k x$ (with $x$ odd) and $2^{i}$ is the largest power of two greater than $N$, $2^{l}$ is the largest power of two greater than $x$, we can set $D=2^{i-1}$, $M = 2^{l-1}$. Informally if $N$ has $i$ bits, then you can  safely expand the most significant bit of $N$ adding $j 2^{i-1}$ and the result will change by $j 2^{l-1}$.  
> **username_0**: typo ... replace "largest power" with "smaller power" :)  
> **username_1**: Oh I see, so D and M can depend on N! This way the statement is much more believable...  

---

## 1 answers

### Answer by username_0 on 2014-02-22. Score: 10 | Accepted answer

The problem has been solved in:

Oscar H. Ibarra, Nicholas Q. Trân, A note on simple programs with two variables, Theoretical Computer Science, Volume 112, Issue 2, 10 May 1993, Pages 391-397, ISSN 0304-3975, [http://dx.doi.org/10.1016/0304-3975(93)90028-R](http://dx.doi.org/10.1016/0304-3975%2893%2990028-R).

Let $TV$ be the class of languages recognized by two-counter machines.

> **Theorem 3.3**: For any fixed integer $k \geq 2$, $L\_k = \{ n^k \mid n \geq 0 \} \notin TV$

Note: it's strange that in the Ibarra&Tran's paper

> **Theorem 3.4** Let $f$ be a total function with infinite range and such that the relation $f(a + bn)=f(a)+cn$ for all $n \geq 0$ does not hold for any triple $(a,b,c)$; then $f$ cannot be computed by any two-counter machine.

is proved and the authors say that it has been derived in a slightly different form in:

I.M. Barzdin, Ob odnom klasse machin Turinga (machiny Minskogo), Russian, *Algebra i Logika* 1 (1963) 42-51

but don't cite Rich Schroeppel's paper (1972) in which the theorem is also derived ... :-)

> **Comments:**
> **username_2**: I'm not sure that it's ever strange that a twenty-year-old paper doesn't get cited: presumably the authors didn't know about it and nor did the referees.  
> **username_0**: @DavidRicherby: I would be curious to see how the theorem in Schroeppel (1972) differs from the corresponding one in Barzdin (1963) :-) ... but I don't have access to the Barzdin's paper  

---

