14

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

András Salamon
  • 19,000
  • 3
  • 64
  • 150
Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • 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
  • typo ... replace "largest power" with "smaller power" :) – Marzio De Biasi Feb 15 '14 at 23:34
  • Oh I see, so D and M can depend on N! This way the statement is much more believable... – domotorp Feb 16 '14 at 06:18

1 Answers1

10

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

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • 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 02 '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 02 '14 at 23:51