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

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

  • $\begingroup$ 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... $\endgroup$
    – domotorp
    Feb 15 '14 at 21:11
  • $\begingroup$ Now I'll look at it, but are you sure that "the largest odd divisor of N" is computable by a 2CM? $\endgroup$ Feb 15 '14 at 21:18
  • $\begingroup$ @domotorp: by the way I asked the same question also on mathoverflow, but didn't get new ideas $\endgroup$ Feb 15 '14 at 21:24
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Feb 15 '14 at 22:02
  • $\begingroup$ 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}$. $\endgroup$ 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 ... :-)

  • $\begingroup$ 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. $\endgroup$ Mar 2 '14 at 14:27
  • $\begingroup$ @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 $\endgroup$ Mar 2 '14 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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