<p>So people keep nagging me to post this even though it only solves a simplified
version of the problem.  Okay then :)</p>

<p>At the end of this, I will put some of what I learned from the paper of Ibarra and Trân, and why <em>that</em> method breaks down on our general problem, but perhaps still gives some useful information.</p>

<p>But first, we'll look at the simpler problem of trying to decide the set </p>

<p>$L = \{ 2^n \mid $ the ternary and binary representations of $2^n$ have both even length or odd length$\}$</p>

<p>Note how this has $2^n$ rather than $n$ as in the original problem.  In particular if the input number is <em>not</em> a power of 2, we want to reject it rather than attempt to calculate its length in any base.</p>

<p>This greatly simplifies matters: If the original number is written prime factorized as $2^{v_2} 3^{v_3} 5^{v_5} 7^{v_7} ...$, then for all the $v_i$ except $v_2$ we just need to check that they are all $0$.</p>

<p>This allows us to solve this simplified problem by using a wrapper around the old method (by Minsky I assume) of encoding the state of a $k$-counter automaton in the exponents of the prime factorization of the single variable of a multiplication/division automaton, which as noted in the OP above is pretty much equivalent to a 2-counter automaton.</p>

<p>First, we need a $k$-counter automaton to wrap.  We will use 3 counters, named $v_2$, $v_3$ and $v_5$.</p>

<p>The automaton will accept iff for the initial counter values, the ternary and binary representations of $2^{v_2}$ have both even length or odd length, <em>and</em> both $v_3$ and $v_5$ are zero.  When it accepts it will first zero all its counters.</p>

<p>Here is some code for that, in an assembly format similar to the OP (I've just added variables to the instructions).  I haven't actually tested it, since I have nothing to run it with, but I consider this a formality: 3-counter automata are well known to be Turing-complete, and to be able to construct any computable function of one of their initial values.</p>

<pre><code>// Check that v3 and v5 are both zero.
                JZ v3, check5
                GOTO reject
check5:         JZ v5, init3
                GOTO reject
// Decrement v2 until it is zero, constructing 2^n in the process.  If 2^n
// was even, we will then pass to even2 with 2^n in v3; If 2^n was odd, we
// will pass to odd2 with 2^n in v5.
init3:          INC v3          // Set v3 to 1 = 2^0 to start with.
even1:          // We have decremented v2 an even number of times so far.
                // 2^decremented amount is in v3.
                JZ v2, odd2
                DEC v2
dup3to5:        JZ v3, odd1
                DEC v3
                INC v5
                INC v5
                GOTO dup3to5
odd1:           // We have decremented v2 an odd number of times so far.
                // 2^decremented amount is in v5.
                JZ v2, even2
                DEC v2
dup5to3:        JZ v5, even1
                DEC v5
                INC v3
                INC v3
                GOTO dup5to3
// The second part checks the ternary length of 2^n, which starts out in v3
// or v5 according to whether the *binary* length of 2^n (i.e. n+1) was odd
// or even.
odd2:           // v3 needs to have odd ternary length to accept.
                // It is simplest to consider 0 to have even length in both
                // binary and ternary.  This works out as long as we're
                // consistent.
                JZ v3, reject
trisect3to5:    DEC v3
                DEC v3
                JZ v3, even2
                DEC v3
                INC v5
                GOTO trisect3to5
even2:          // v5 needs to have even ternary length to accept
                JZ v5, accept
trisect5to3:    DEC v5
                DEC v5
                JZ v5, odd2
                DEC v5
                INC v3
                GOTO trisect5to3
accept:         HALT Accept
reject:         HALT Reject
</code></pre>

<p>The next step is then to re-encode the above in the exponents of a single variable automaton.  As the result is pretty long, I'll just describe the general method, but a <a href="http://oerjan.nvg.org/math/2ca.txt" rel="nofollow">full version</a> (slightly "optimized" in spots) is on my website.</p>

<pre><code>                JZ vp, label
                DEC vp
next:           ...
</code></pre>

<p>becomes (basically divide by p, and then do cleanup to undo if the division wasn't even):</p>

<pre><code>                DIV p, next, ..., newlabel.fp-1
newlabel.f1:    MUL p
                GOTO newlabel.i1
...
newlabel.fp-1:  MUL p
                INC
newlabel.ip-2:  INC
...
newlabel.i1:    INC
                GOTO label
next:           ...
</code></pre>

<p><code>INC vp</code> becomes <code>MUL p</code>. Individual <code>JZ</code> and <code>DEC</code> can first be changed into the combined form.  <code>GOTO label</code> and <code>HALT Reject</code> are unchanged.</p>

<p><code>HALT Accept</code> would be unchanged, except that in our case we still have one final check to do: we need to ensure that there are no prime factors in the number <em>other</em> than 2,3 and 5.  Since our particular 3-counter automaton zeros the counters it uses when it accepts, this is simple: just test that the final variable is 1, which can be done by jumping to the code</p>

<pre><code>                DEC     // BTW it cannot be zero before this.
                JZ accept
                HALT Reject
accept:         HALT Accept
</code></pre>

<p>The code on my website also has an <em>initial</em> check that the number isn't zero, which I've just realized is redundant with the v3, v5 zero checks, oh well.</p>

<p>As I mentioned, the above method works for the simplified problem, but it really has <em>no</em> chance of working for the general one, because:  In the general problem the precise value of <em>every</em> prime's exponent counts for deciding its general size and thus which lengths it has in various bases.  This means that:</p>

<ul>
<li>We have no "free" primes to use for counters.</li>
<li>Even if we <em>did</em> have free primes for counters, we don't really have a way to extract all the necessary information from the infinitely many other primes whose exponent values <em>do</em> matter.</li>
</ul>

<p>So let's end with an explanation of the gist of the general method from the above linked <a href="http://dl.acm.org/citation.cfm?id=151866" rel="nofollow">paper by Ibarra and Trân</a> (<a href="http://www.sciencedirect.com/science/article/pii/030439759390028R" rel="nofollow">freely downloadable version</a>) for how to prove that certain problems <em>aren't</em> solvable by a 2CA, and how it annoyingly breaks down in our case.</p>

<p>First, they modify every 2CA into a "normal form", in which the two counters switch in "phases" between one only increasing and the other only decreasing until it reaches zero.  The number of states $s$ of this normalized automaton plays an important role in the estimates.</p>

<p>Then, they analyze this automaton to conclude that they can construct certain arithmetic sequences of numbers whose behavior are linked.  To be precise (Some of this is not stated as theorems, but is implicit in the proof of both of their two main examples):</p>

<ol>
<li>If a number x is accepted by the automaton, without the size $v^x_i$ of the nonzero counter at the beginning of a phase $i$ <em>ever</em> going $\leq s$, then there exists an integer $D&gt;0$ such that <em>all</em> the numbers $x + n D$, $n\geq 0$ are accepted.</li>
<li><p>If a set $X$ contains at least $s^2+1$ accepted numbers such that for each number $x\in X$ there is a phase $i$ such that $v^x_i\leq s$, then we can find $p, r\in X$, and integers $K_1,K_2$ such that</p>

<ul>
<li>For every integer $n\geq 0$, either $p + n K_1$ and $r + n K_2$ are both accepted by the automaton, or both are rejected.</li>
</ul></li>
</ol>

<p>(Thoughts:</p>

<ul>
<li>They require $x&gt;s$ for $x\in X$ but I think this is actually unnecessary.  Actually so is that they are accepted.</li>
<li>Most of this should also hold for <em>rejected</em> numbers, as long as the rejection is by explicit halting rather than nontermination.)</li>
</ul>

<p>For their own examples they also frequently use the fact that $D,K_1,K_2$ have no prime factors $&gt;s$.  To prove impossibility, they then derive contradictions by showing that such arithmetical sequences cannot exist.</p>

<p>In our problem, getting a contradiction from this breaks down with the second case.  If we have $K_1 = K_2 = 6^k$, where $k$ is large enough that <em>no</em> number between $p$ and $r$ is divisible by either $2^k$ or $3^k$, then there will also be no powers of 2 or 3 between $p + 6^k n$ and $q + 6^k n$, so they are either both accepted or both rejected.</p>

<p>Point 1 can still be shown to be impossible, because powers of 2 and 3 mostly grow further and further apart.  And I believe I can show the second case impossible if $K_1\neq K_2$ (I've emailed @MarzioDeBiasi the argument).  So perhaps someone could use this information to restrict the form of the automaton further, and finally derive a contradiction from that.</p>

CC BY-SA 3.0
2015-01-19T08:53:56.123Z
Very good and clear answer!
Marzio De Biasi
CC BY-SA 3.0
2015-01-19T02:07:40.143Z
2015-01-19T16:41:04.240Z
2015-01-19T16:41:04.240Z
Ørjan Johansen
<p>I would like to prove (or disprove) the following conjecture:</p>

<p><b>Conjecture</b>: a <a href="http://en.wikipedia.org/wiki/Counter_machine">two counter automata</a> (2CA) cannot decide the following language:</p>

<p>$L = \{ n \mid $ the ternary and binary representations of $n$ have both even length or odd length$\}$</p>

<p>A 2CA can easily check if the binary representation has even or odd length (just keep dividing by two and update an "even length" flag after each division); in the same manner it can check if the ternary representation has even or odd length (just keep dividing by three and update an "even length" flag after each division).</p>

<p>But in order to calculate one of them it must <strong>destroy</strong> its input, and cannot recover it to calculate the other; so it seems that there is no way to decide $L$.</p>

<blockquote>
Do you know a technique that can be used to prove the conjecture?<br>
Or can you disprove the conjecture building a 2CA that decides $L$?
</blockquote>

<p>I tried the same approach followed by Ibarra to prove that a <a href="http://dl.acm.org/citation.cfm?id=151866">2CA cannot decide $\{n^2\mid n \geq 1\}$</a>, but it seems not the right way.</p>

<p><b>Note</b>: for simplicity a 2CA is equivalent to a program with <b>one</b> variable $c$  that initially contains the input and the following instruction set:</p>

<ul>
<li><b>INC</b>: add one to the variable;</li>
<li><b>DEC</b>: decrement $c$ (only if it is greater than zero);</li>
<li><b>JZ  $lab$</b>: if $c$ is zero jump to label $lab$ otherwise continue;</li>
<li><b>MUL $K$</b>: multiply $c$ by the costant $K$;</li>
<li><b>DIV $K [, lab_0, lab_1,...,lab_{K-1}]$</b>: divide $c$ by the constant $K$ and store the  quotient to $c$ ($c = \lfloor c / K \rfloor$); possibly jump to different labels according to the remainder ($c \bmod K$);</li>
<li><b>GOTO $lab$</b>: unconditional jump;</li>
<li><b>HALT Accept|Reject</b>: halt and accept or halt and reject.</li>
</ul>

<p>For example a program to check if the binary representation of $n$ has even length is:</p>

<pre><code>   loop: JZ even   // test if n = 0
         DIV 2
         JZ odd    // test if n = 0
         DIV 2
         GOTO loop
   even: HALT Accept
    odd: HALT Reject
</code></pre>

<p>(we can build an equivalent 2CA)</p>

CC BY-SA 3.0
2014-05-16T04:02:51.160Z
Oh, ok.  Cool.  I get it now.  :)
Michael Wehar
CC BY-SA 3.0
2015-01-13T13:38:21.183Z
@MichaelWehar: I didn't work on the problem for a long, however the last attempts I made were on the (simpler???) language $\{ 2^n \mid $ the ternary representation of $2^n$ has odd length $\}$. If you have some ideas let me know (see email on the linked blog in my profile).
Marzio De Biasi
CC BY-SA 3.0
2015-01-14T00:08:48.490Z
I don't know how the impossibility proofs go, but the {$2^n$∣ the ternary representation of $2^n$ has odd length } case *is* solvable, because whenever your input has only known prime factors you can treat your exponents (n here) as counters in a simulated automaton with as many counters (simulated by extra primes) as you want, thus Turing-complete.
Ørjan Johansen
CC BY-SA 3.0
2015-01-14T00:10:18.857Z
@ØrjanJohansen: In order to accept, you must check that the input (the counter value) is effectively $2^n$ (i.e. a power of two) and *at the same time* check that its ternary representation has odd length.
Marzio De Biasi
CC BY-SA 3.0
2015-01-14T00:21:45.717Z
Oh, I didn't think of that, I assumed it was known that it was of the form $2^n$. But I think I have an idea that gets around that. (1) Assume c is of the form $a 2^n$ where $a$ is odd. (2) Check whether c is divisible by 3,5,7 up to as many counters as you need for step 3, if so it obviously fails. (3) *Ignoring* the $a$ part, run a program using the primes excluded in step 2 to check whether just the $2^n$ part has the right properties. (4) Divide out all 2s and primes used in step 3, if this doesn't result in c=1, also fail.
Ørjan Johansen
CC BY-SA 3.0
2015-01-14T00:42:00.740Z
Of course this is not new; I notice in the introduction to your linked article by Ibarra "[...] for every recursive set S, the set S' = $\{2^s:s\in S\}$ is in TV."
Ørjan Johansen
CC BY-SA 3.0
2015-01-14T07:46:35.820Z
@ØrjanJohansen: perhaps you missed something, the property is not about the ternary expansion of $n$, but about the ternary expansion of $2^n$: $2 = 2_3 \in L$, $4 = 11_3 \notin L$, $8 = 22_3 \notin L$, $16 = 121_3 \in L$, $32 = 1012_3 \notin L$, ....
Marzio De Biasi
CC BY-SA 3.0
2015-01-15T01:16:43.137Z
No I didn't miss that, I just didn't specify step 3 very precisely because once you have a few extra primes to use for simulated counters in a larger automaton, the system is Turing-complete and you can calculate whatever temporary functions of $n$ you want, including $2^n$.
Ørjan Johansen
CC BY-SA 3.0
2015-01-15T01:28:25.743Z
Basically I'm alluding in step 3 to the kind of Gödel numbering method described in [Wikipedia's counter machine article](https://en.wikipedia.org/wiki/Counter_machine#Step_3:_Four_counters_can_be_simulated_by_two_counters.), and the other steps are just to be able to detect and reject if there are other primes than $2$ present in the original input.
Ørjan Johansen
CC BY-SA 3.0
2015-01-15T17:35:16.080Z
I didn't want to post it as an answer because it only solves a simpler problem than your main question. The trick is that the check is divided: Step 2 doesn't destroy the input because it only checks primes 3,5,7 up to as many as we need for temporaries in the calculation in step 3. It does not touch the number of 2s at all. Step 4 completes the check for all other primes by destroying the value, but only *after* we've already done the necessary calculations in step 3 on the $2^n$ part.
Ørjan Johansen
CC BY-SA 3.0
2015-01-15T19:13:04.150Z
@ØrjanJohansen: I think it doesn't work; if you want email me; we should not flood the comments area.
Marzio De Biasi
CC BY-SA 3.0
2015-01-16T05:27:05.950Z
I emailed you some "code", and also put it [on my website](http://oerjan.nvg.org/math/2ca.txt) in case anyone else is watching.
Ørjan Johansen
CC BY-SA 3.0
2015-01-16T08:42:09.247Z
@ØrjanJohansen: G.R.E.A.T.YOU ARE RIGHT, reading the comments I missed that checking if the input is not divisible by 3 and 5 can be done in a single pass (and the input recovered). Then your idea for the simpler version of the problem is ok: you can check that $3 \nmid c$ and $5 \nmid c$ then go from $2^n 3^0 5^0$ to $2^n 3^n 5^0$, then use the universal capabilities of the "virtual" counters 3,5 to check everything about n (in particular if $2^n$ has the same representation length in base 2 and 3), and finally check the initial untouched $2^n$.
Marzio De Biasi
CC BY-SA 3.0
2015-01-17T03:44:43.290Z
@ØrjanJohansen did you test it with a simulator? do you have a writeup of the ideas not in stackexchange or code comments? if its the answer then why dont you write it up? you have 3 days to get 100 pts from MW
vzn
CC BY-SA 3.0
2015-01-17T09:06:49.710Z
@vzn I don't have a simulator to test it with, but I think none of this is really new. Minsky's idea that you can encode several counters in two counters, or in one variable with mul/div is old. And it's not *the* answer because it's answering a (in practice much) simpler question than the main one in this post.
Ørjan Johansen
CC BY-SA 3.0
2015-01-17T16:00:51.810Z
@ØrjanJohansen a simulator would help catch coding errors & ensure validity. ok how about writing up the partial answer which clearly involves significant work, detail what gap remains, allowing others to build on it & let audience respond.
vzn
CC BY-SA 3.0
2015-01-18T12:12:56.493Z
Since the linked code uses additional counters, if additional counters are allowed can't one solve by incrementing $2^k \le n < 2^{k+1},3^m \le n < 3^{m+1}$ for counters $k,m$ ?
joro
CC BY-SA 3.0
2015-01-18T13:04:49.967Z
@ØrjanJohansen Can you solve (possibly by incrementing) $2^k \le n < 2^{k+1},3^m \le n < 3^{m+1}$ for counters $k,m$? I suppose this will solve the problem.
joro
CC BY-SA 3.0
2015-01-18T22:42:10.047Z
@joro The method I described has a strict limitation: it can only handle finitely many prime factors of the input (except for testing if the remainder are all 0 or not.)  The problem is that in the general problem, the exponents of *all* prime factors count. You can actually calculate *either* your $k$ or your $m$ up to parity, but as far as I know, there is no way to compare a general input to $2^k$ or $3^m$ without destroying it in the process, so that you cannot test the *other* one afterwards. My hunch right now is that the general problem is unsolvable with a 2CA.
Ørjan Johansen
CC BY-SA 3.0
2015-01-18T22:51:00.760Z
@ØrjanJohansen: I agree with vzn: if you want, you can post the answer with the solution to the restricted simpler problem (worth the bounty :-) and can be of help to those who wants to quickly get  into the original problem). You can also *VERY briefly* note why the Ibarra's approach fails for the general problem, and why the solution of the simpler version fails for the general one (copy-paste the comment to joro).
Marzio De Biasi
CC BY-SA 3.0
2015-01-19T02:08:58.003Z
@MarzioDeBiasi OK I finally did, although I think I may have stretched the VERY *briefly* part...
Ørjan Johansen
CC BY-SA 3.0
2015-01-19T17:05:56.143Z
_thx!_ great/ rare to see all the interest/ activity in this problem. a few [more comments/ questions](http://chat.stackexchange.com/transcript/message/19613287#19613287) on this problem
vzn
<automata-theory>
Conjecture about two counters automata
Marzio De Biasi
# Conjecture about two counters automata

(Asked by: username_0 on 2014-03-13)

I would like to prove (or disprove) the following conjecture:
Conjecture: a two counter automata (2CA) cannot decide the following language:
$L = \{ n \mid $ the ternary and binary representations of $n$ have both even length or odd length$\}$
A 2CA can easily check if the binary representation has even or odd length (just keep dividing by two and update an "even length" flag after each division); in the same manner it can check if the ternary representation has even or odd length (just keep dividing by three and update an "even length" flag after each division).
But in order to calculate one of them it must destroy its input, and cannot recover it to calculate the other; so it seems that there is no way to decide $L$.

Do you know a technique that can be used to prove the conjecture?
Or can you disprove the conjecture building a 2CA that decides $L$?

I tried the same approach followed by Ibarra to prove that a 2CA cannot decide $\{n^2\mid n \geq 1\}$, but it seems not the right way.
Note: for simplicity a 2CA is equivalent to a program with one variable $c$  that initially contains the input and the following instruction set:

INC: add one to the variable;
DEC: decrement $c$ (only if it is greater than zero);
JZ  $lab$: if $c$ is zero jump to label $lab$ otherwise continue;
MUL $K$: multiply $c$ by the costant $K$;
DIV $K [, lab_0, lab_1,...,lab_{K-1}]$: divide $c$ by the constant $K$ and store the  quotient to $c$ ($c = \lfloor c / K \rfloor$); possibly jump to different labels according to the remainder ($c \bmod K$);
GOTO $lab$: unconditional jump;
HALT Accept|Reject: halt and accept or halt and reject.

For example a program to check if the binary representation of $n$ has even length is:
   loop: JZ even   // test if n = 0
         DIV 2
         JZ odd    // test if n = 0
         DIV 2
         GOTO loop
   even: HALT Accept
    odd: HALT Reject

(we can build an equivalent 2CA)

**Tags:** automata-theory
> **Comments:**
> **username_1**: Oh, ok.  Cool.  I get it now.  :)  
> **username_0**: @MichaelWehar: I didn't work on the problem for a long, however the last attempts I made were on the (simpler???) language $\{ 2^n \mid $ the ternary representation of $2^n$ has odd length $\}$. If you have some ideas let me know (see email on the linked blog in my profile).  
> **username_2**: I don't know how the impossibility proofs go, but the {$2^n$∣ the ternary representation of $2^n$ has odd length } case *is* solvable, because whenever your input has only known prime factors you can treat your exponents (n here) as counters in a simulated automaton with as many counters (simulated by extra primes) as you want, thus Turing-complete.  
> **username_0**: @ØrjanJohansen: In order to accept, you must check that the input (the counter value) is effectively $2^n$ (i.e. a power of two) and *at the same time* check that its ternary representation has odd length.  
> **username_2**: Oh, I didn't think of that, I assumed it was known that it was of the form $2^n$. But I think I have an idea that gets around that. (1) Assume c is of the form $a 2^n$ where $a$ is odd. (2) Check whether c is divisible by 3,5,7 up to as many counters as you need for step 3, if so it obviously fails. (3) *Ignoring* the $a$ part, run a program using the primes excluded in step 2 to check whether just the $2^n$ part has the right properties. (4) Divide out all 2s and primes used in step 3, if this doesn't result in c=1, also fail.  
> **username_2**: Of course this is not new; I notice in the introduction to your linked article by Ibarra "[...] for every recursive set S, the set S' = $\{2^s:s\in S\}$ is in TV."  
> **username_0**: @ØrjanJohansen: perhaps you missed something, the property is not about the ternary expansion of $n$, but about the ternary expansion of $2^n$: $2 = 2_3 \in L$, $4 = 11_3 \notin L$, $8 = 22_3 \notin L$, $16 = 121_3 \in L$, $32 = 1012_3 \notin L$, ....  
> **username_2**: No I didn't miss that, I just didn't specify step 3 very precisely because once you have a few extra primes to use for simulated counters in a larger automaton, the system is Turing-complete and you can calculate whatever temporary functions of $n$ you want, including $2^n$.  
> **username_2**: Basically I'm alluding in step 3 to the kind of Gödel numbering method described in [Wikipedia's counter machine article](https://en.wikipedia.org/wiki/Counter_machine#Step_3:_Four_counters_can_be_simulated_by_two_counters.), and the other steps are just to be able to detect and reject if there are other primes than $2$ present in the original input.  
> **username_2**: I didn't want to post it as an answer because it only solves a simpler problem than your main question. The trick is that the check is divided: Step 2 doesn't destroy the input because it only checks primes 3,5,7 up to as many as we need for temporaries in the calculation in step 3. It does not touch the number of 2s at all. Step 4 completes the check for all other primes by destroying the value, but only *after* we've already done the necessary calculations in step 3 on the $2^n$ part.  
> **username_0**: @ØrjanJohansen: I think it doesn't work; if you want email me; we should not flood the comments area.  
> **username_2**: I emailed you some "code", and also put it [on my website](http://oerjan.nvg.org/math/2ca.txt) in case anyone else is watching.  
> **username_0**: @ØrjanJohansen: G.R.E.A.T.YOU ARE RIGHT, reading the comments I missed that checking if the input is not divisible by 3 and 5 can be done in a single pass (and the input recovered). Then your idea for the simpler version of the problem is ok: you can check that $3 \nmid c$ and $5 \nmid c$ then go from $2^n 3^0 5^0$ to $2^n 3^n 5^0$, then use the universal capabilities of the "virtual" counters 3,5 to check everything about n (in particular if $2^n$ has the same representation length in base 2 and 3), and finally check the initial untouched $2^n$.  
> **username_3**: @ØrjanJohansen did you test it with a simulator? do you have a writeup of the ideas not in stackexchange or code comments? if its the answer then why dont you write it up? you have 3 days to get 100 pts from MW  
> **username_2**: @vzn I don't have a simulator to test it with, but I think none of this is really new. Minsky's idea that you can encode several counters in two counters, or in one variable with mul/div is old. And it's not *the* answer because it's answering a (in practice much) simpler question than the main one in this post.  
> **username_3**: @ØrjanJohansen a simulator would help catch coding errors & ensure validity. ok how about writing up the partial answer which clearly involves significant work, detail what gap remains, allowing others to build on it & let audience respond.  
> **username_4**: Since the linked code uses additional counters, if additional counters are allowed can't one solve by incrementing $2^k \le n < 2^{k+1},3^m \le n < 3^{m+1}$ for counters $k,m$ ?  
> **username_4**: @ØrjanJohansen Can you solve (possibly by incrementing) $2^k \le n < 2^{k+1},3^m \le n < 3^{m+1}$ for counters $k,m$? I suppose this will solve the problem.  
> **username_2**: @joro The method I described has a strict limitation: it can only handle finitely many prime factors of the input (except for testing if the remainder are all 0 or not.)  The problem is that in the general problem, the exponents of *all* prime factors count. You can actually calculate *either* your $k$ or your $m$ up to parity, but as far as I know, there is no way to compare a general input to $2^k$ or $3^m$ without destroying it in the process, so that you cannot test the *other* one afterwards. My hunch right now is that the general problem is unsolvable with a 2CA.  
> **username_0**: @ØrjanJohansen: I agree with vzn: if you want, you can post the answer with the solution to the restricted simpler problem (worth the bounty :-) and can be of help to those who wants to quickly get  into the original problem). You can also *VERY briefly* note why the Ibarra's approach fails for the general problem, and why the solution of the simpler version fails for the general one (copy-paste the comment to joro).  
> **username_2**: @MarzioDeBiasi OK I finally did, although I think I may have stretched the VERY *briefly* part...  
> **username_3**: _thx!_ great/ rare to see all the interest/ activity in this problem. a few [more comments/ questions](http://chat.stackexchange.com/transcript/message/19613287#19613287) on this problem  

---

## 1 answers

### Answer by username_2 on 2015-01-19. Score: 11

So people keep nagging me to post this even though it only solves a simplified
version of the problem.  Okay then :)
At the end of this, I will put some of what I learned from the paper of Ibarra and Trân, and why that method breaks down on our general problem, but perhaps still gives some useful information.
But first, we'll look at the simpler problem of trying to decide the set 
$L = \{ 2^n \mid $ the ternary and binary representations of $2^n$ have both even length or odd length$\}$
Note how this has $2^n$ rather than $n$ as in the original problem.  In particular if the input number is not a power of 2, we want to reject it rather than attempt to calculate its length in any base.
This greatly simplifies matters: If the original number is written prime factorized as $2^{v_2} 3^{v_3} 5^{v_5} 7^{v_7} ...$, then for all the $v_i$ except $v_2$ we just need to check that they are all $0$.
This allows us to solve this simplified problem by using a wrapper around the old method (by Minsky I assume) of encoding the state of a $k$-counter automaton in the exponents of the prime factorization of the single variable of a multiplication/division automaton, which as noted in the OP above is pretty much equivalent to a 2-counter automaton.
First, we need a $k$-counter automaton to wrap.  We will use 3 counters, named $v_2$, $v_3$ and $v_5$.
The automaton will accept iff for the initial counter values, the ternary and binary representations of $2^{v_2}$ have both even length or odd length, and both $v_3$ and $v_5$ are zero.  When it accepts it will first zero all its counters.
Here is some code for that, in an assembly format similar to the OP (I've just added variables to the instructions).  I haven't actually tested it, since I have nothing to run it with, but I consider this a formality: 3-counter automata are well known to be Turing-complete, and to be able to construct any computable function of one of their initial values.
// Check that v3 and v5 are both zero.
                JZ v3, check5
                GOTO reject
check5:         JZ v5, init3
                GOTO reject
// Decrement v2 until it is zero, constructing 2^n in the process.  If 2^n
// was even, we will then pass to even2 with 2^n in v3; If 2^n was odd, we
// will pass to odd2 with 2^n in v5.
init3:          INC v3          // Set v3 to 1 = 2^0 to start with.
even1:          // We have decremented v2 an even number of times so far.
                // 2^decremented amount is in v3.
                JZ v2, odd2
                DEC v2
dup3to5:        JZ v3, odd1
                DEC v3
                INC v5
                INC v5
                GOTO dup3to5
odd1:           // We have decremented v2 an odd number of times so far.
                // 2^decremented amount is in v5.
                JZ v2, even2
                DEC v2
dup5to3:        JZ v5, even1
                DEC v5
                INC v3
                INC v3
                GOTO dup5to3
// The second part checks the ternary length of 2^n, which starts out in v3
// or v5 according to whether the *binary* length of 2^n (i.e. n+1) was odd
// or even.
odd2:           // v3 needs to have odd ternary length to accept.
                // It is simplest to consider 0 to have even length in both
                // binary and ternary.  This works out as long as we're
                // consistent.
                JZ v3, reject
trisect3to5:    DEC v3
                DEC v3
                JZ v3, even2
                DEC v3
                INC v5
                GOTO trisect3to5
even2:          // v5 needs to have even ternary length to accept
                JZ v5, accept
trisect5to3:    DEC v5
                DEC v5
                JZ v5, odd2
                DEC v5
                INC v3
                GOTO trisect5to3
accept:         HALT Accept
reject:         HALT Reject

The next step is then to re-encode the above in the exponents of a single variable automaton.  As the result is pretty long, I'll just describe the general method, but a full version (slightly "optimized" in spots) is on my website.
                JZ vp, label
                DEC vp
next:           ...

becomes (basically divide by p, and then do cleanup to undo if the division wasn't even):
                DIV p, next, ..., newlabel.fp-1
newlabel.f1:    MUL p
                GOTO newlabel.i1
...
newlabel.fp-1:  MUL p
                INC
newlabel.ip-2:  INC
...
newlabel.i1:    INC
                GOTO label
next:           ...

INC vp becomes MUL p. Individual JZ and DEC can first be changed into the combined form.  GOTO label and HALT Reject are unchanged.
HALT Accept would be unchanged, except that in our case we still have one final check to do: we need to ensure that there are no prime factors in the number other than 2,3 and 5.  Since our particular 3-counter automaton zeros the counters it uses when it accepts, this is simple: just test that the final variable is 1, which can be done by jumping to the code
                DEC     // BTW it cannot be zero before this.
                JZ accept
                HALT Reject
accept:         HALT Accept

The code on my website also has an initial check that the number isn't zero, which I've just realized is redundant with the v3, v5 zero checks, oh well.
As I mentioned, the above method works for the simplified problem, but it really has no chance of working for the general one, because:  In the general problem the precise value of every prime's exponent counts for deciding its general size and thus which lengths it has in various bases.  This means that:

We have no "free" primes to use for counters.
Even if we did have free primes for counters, we don't really have a way to extract all the necessary information from the infinitely many other primes whose exponent values do matter.

So let's end with an explanation of the gist of the general method from the above linked paper by Ibarra and Trân (freely downloadable version) for how to prove that certain problems aren't solvable by a 2CA, and how it annoyingly breaks down in our case.
First, they modify every 2CA into a "normal form", in which the two counters switch in "phases" between one only increasing and the other only decreasing until it reaches zero.  The number of states $s$ of this normalized automaton plays an important role in the estimates.
Then, they analyze this automaton to conclude that they can construct certain arithmetic sequences of numbers whose behavior are linked.  To be precise (Some of this is not stated as theorems, but is implicit in the proof of both of their two main examples):

If a number x is accepted by the automaton, without the size $v^x_i$ of the nonzero counter at the beginning of a phase $i$ ever going $\leq s$, then there exists an integer $D>0$ such that all the numbers $x + n D$, $n\geq 0$ are accepted.
If a set $X$ contains at least $s^2+1$ accepted numbers such that for each number $x\in X$ there is a phase $i$ such that $v^x_i\leq s$, then we can find $p, r\in X$, and integers $K_1,K_2$ such that

For every integer $n\geq 0$, either $p + n K_1$ and $r + n K_2$ are both accepted by the automaton, or both are rejected.


(Thoughts:

They require $x>s$ for $x\in X$ but I think this is actually unnecessary.  Actually so is that they are accepted.
Most of this should also hold for rejected numbers, as long as the rejection is by explicit halting rather than nontermination.)

For their own examples they also frequently use the fact that $D,K_1,K_2$ have no prime factors $>s$.  To prove impossibility, they then derive contradictions by showing that such arithmetical sequences cannot exist.
In our problem, getting a contradiction from this breaks down with the second case.  If we have $K_1 = K_2 = 6^k$, where $k$ is large enough that no number between $p$ and $r$ is divisible by either $2^k$ or $3^k$, then there will also be no powers of 2 or 3 between $p + 6^k n$ and $q + 6^k n$, so they are either both accepted or both rejected.
Point 1 can still be shown to be impossible, because powers of 2 and 3 mostly grow further and further apart.  And I believe I can show the second case impossible if $K_1\neq K_2$ (I've emailed @MarzioDeBiasi the argument).  So perhaps someone could use this information to restrict the form of the automaton further, and finally derive a contradiction from that.

> **Comments:**
> **username_0**: Very good and clear answer!  

---

