# N^2 and two counter machines

I asked this question on cstheory a few months ago, 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]

(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.

• It looks to me like in the question on cstheory there are two registers whereas here I see only one. What am I missing? – Noah Stein Feb 12 '14 at 16:28
• It appears to me the problem is equivalent to the following: is there a constant $c>0$ and a unary integer function $f$ definable in Presburger arithmetic such that for every $n$, the iterates $f^{(k)}(cn)$ eventually stabilize in a fixpoint, and $n$ is a square iff the fixpoint is (say) $0$. – Emil Jeřábek Feb 12 '14 at 16:49
• @NoahStein: The two formulations are equivalent (see Schroeppel's paper), the one I gave here is called More Powerful 1 Register Machine (MP1RM). In the 2 counter version there are no div/mul operations. – Marzio De Biasi Feb 12 '14 at 16:58
• The only paper at MathSciNet that references Schroeppel's paper is MR2440596 (2009e:03073); Dershowitz, Nachum; Gurevich, Yuri; A natural axiomatization of computability and proof of Church's Thesis. Bull. Symbolic Logic 14 (2008), no. 3, 299–350. – Gerry Myerson Feb 12 '14 at 22:08
• I didn't mean to express or imply any opinion on whether the problem is still open; I just hoped I could save people the effort of checking something on MathSciNet. It might be worth looking at the Dershowitz-Gurevich paper to see whether they had anything to say about the question, if you haven't already done that. – Gerry Myerson Feb 13 '14 at 0:42

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$