Can a standard two counters ($c_1,c_2$) machine with the following instructions:1) ADD 1 to c_i, GOTO label_j2) IF c_i = 0 GOTO label_j, OTHERWISE SUB 1 to c_i and GOTO label_k3) GOTO label_j4) HALT and ACCEPT|REJECTdecide 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])
Can a two counters machine decide $n^2$?
fl.formal languages;counter automata
The problem has been solved in: Oscar H. Ibarra, Nicholas Q. Trn, 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-51but don't cite Rich Schroeppel's paper (1972) in which the theorem is also derived ... :-)