4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It looks to me like in the question on cstheory there are two registers whereas here I see only one. What am I missing? $\endgroup$ – Noah Stein Feb 12 '14 at 16:28
  • $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek Feb 12 '14 at 16:49
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Feb 12 '14 at 16:58
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Feb 12 '14 at 22:08
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Feb 13 '14 at 0:42
2
$\begingroup$

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$
| cite | improve this answer | |
$\endgroup$

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.