# Can a two counters machine decide $n^2$?

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

• 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 Feb 15 '14 at 21:11
• 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 Feb 15 '14 at 21:18
• @domotorp: by the way I asked the same question also on mathoverflow, but didn't get new ideas – Marzio De Biasi Feb 15 '14 at 21:24
• 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 Feb 15 '14 at 22:02
• 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 Feb 15 '14 at 23:19

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.

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 ... :-)

• 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 Mar 2 '14 at 14:27
• @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 Mar 2 '14 at 23:51