I asked this [question on cstheory a few months ago](https://cstheory.stackexchange.com/questions/19551/can-a-two-counters-machine-decide-n2), but I didn't receive an answer, so I'm posting it here to see if there are original ideas from the "math world" to solve it. The original question asks about recognizing the language $L = \{N^2 \mid N \geq 1\}$ on a two counter machine, but I'll give here an equivalent formulation.


Suppose that you can write a program on a machine equipped with a single integer register $R$ and the following instruction set:


* **Add $K$** : adds a constant $K \geq 0$ to the register;
* **Mul $K$** : multiplies the register by $K \geq 0$;
* **DJZ $lab$** : subtract one from the register, if the result is zero jump to label $lab$; otherwise continue with the next instruction;
* **Div $K, lab\_0$,$lab\_1$,...,$lab\_{K-1}$** : divide the register by $K>0$, and place the quotient in the register (R = R div K); then jump to one of the $K$ labels according to the remainder (R mod K); the labels are not necessarily distinct;
* **Jump $lab$** : unconditional jump to label $lab$
* **Halt (ACCEPT|REJECT)** : stop the computation and ACCEPT or REJECT


Every instruction can have a label.


The question is:



> 
> If the register $R$ is initially loaded with an integer $M \geq 1$, can we build a program that ACCEPTs if and only if $M$ is a square (i.e. $M = N^2$)?
> 


The problem originally appeared in:


[Rich Schroeppel, "A Two counter Machine Cannot Calculate $2^N$" [1972]](http://dspace.mit.edu/bitstream/handle/1721.1/6202/AIM-257.pdf?sequence=2)


(and perhaps has been solved, but I didn't find anything).


Note: in Schroeppel's paper the above model is called *More Powerful One Register Machine* (MP1RM) and is equivalent to a 2 counter machine.



N^2 and two counter machines
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$
> 


