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.

Improve this question
$\endgroup$
6
  • $\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
    Commented Feb 12, 2014 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
    Commented Feb 12, 2014 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
    Commented Feb 12, 2014 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
    Commented Feb 12, 2014 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
    Commented Feb 13, 2014 at 0:42

1 Answer 1

Reset to default
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$
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .