17

2dca's (two-way deterministic one-counter automata) (Petersen, 1994) can recognize the following unary language: \begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{equation}

Is there any other nontrivial unary language recognized by 2dca's?

Remark that it is still unknown whether 2dca's can recognize $ \mathtt{SQUARE} = \lbrace 0^{n^2} \mid n \geq 0 \rbrace $?

DEFINITION: A 2dca is a two-way deterministic finite automaton with a counter. A 2dca can test whether the value of the counter is zero or not, and increment or decrement the value of the counter by 1 in each step.

Community
  • 1
Abuzer Yakaryilmaz
  • 3,707
  • 1
  • 20
  • 38
  • 3
    Could you add a link to a definition of a 2DCA ? – Suresh Venkat Jul 08 '12 at 20:50
  • 3
    @SureshVenkat: I added a reference and also a definition. – Abuzer Yakaryilmaz Jul 08 '12 at 22:00
  • 1
    @AbuzerYakaryilmaz: for every fixed $k$ it can recognize ${0^{k^n} : n \geq 0}$ – Marzio De Biasi May 07 '13 at 17:19
  • @MarzioDeBiasi: The algorithm for $ \mathtt{POWER} $ can be easily generalized to $ \mathtt{POWER_k} = {0^{k^n} \mid n \geq 0} $, where $ k \geq 3 $. Therefore, these languages are quite trivial for me. – Abuzer Yakaryilmaz May 08 '13 at 05:16
  • @AbuzerYakaryilmaz: I thought it might be :-) A curiosity: are you actually/still working on 2DCAs ? – Marzio De Biasi May 08 '13 at 06:50
  • @MarzioDeBiasi: I am interested in quantum generalizations of counter machines. Then, it is natural to examine its their classical counterparts, too. – Abuzer Yakaryilmaz May 08 '13 at 08:29
  • @AbuzerYakaryilmaz: did you read the idea about using the distance from left endmarker as a second counter and augment the power of the 2DCA? Do you think it is a trivial/known approach? – Marzio De Biasi Jun 03 '13 at 07:08
  • @MarzioDeBiasi: Sorry for late response :( I have been traveling for a while and I mostly focused on the protests in Turkey in my free time. I read your idea. I like it very much. I believe that this idea can lead to some new results. Since the simulation by counters uses too much time and space, the second part of the input should be very large. Such a control may be done by probabilistically - I do not know how to do it deterministically. But, personally, I do not expect an arbitrary gap between $n$ and $T'(n)$. I will go on thinking about it and let you know if I end up with some results:) – Abuzer Yakaryilmaz Jun 03 '13 at 12:36
  • Is there any language that can be recognized by a 2DCA but not by one that halts when it first reads the (right) endmarker? – domotorp Jul 15 '13 at 08:22
  • @domotorp: I think $ L = { a^mb^n | m=n \mbox{ or } 2m=n } $ is such a language. I believe that a hierarchy in terms of the number of visiting the right endmarker before halting can be shown not only for deterministic but also notdeterministic model. – Abuzer Yakaryilmaz Jul 15 '13 at 09:57
  • I meant unary language but I see that a similar trick works, e.g., $L={0^{k^n}\mid k=2 \textit{ or } 3}$. So let me modify my question as follows. Is there a unary language that can be recognized by a 2DCA but not by one that reads the (right) endmarker only a bounded number of times? Probably there is and this example should be nontrivial enough. – domotorp Jul 15 '13 at 12:50
  • How about those words whose length's biggest power of two divisor has an odd power? So 2, 6, 8, 10, 14, 18 etc. (For your original question.) – domotorp Jul 15 '13 at 13:30
  • @domotorp: Actually, by modifying the idea given by Marzio De Bassi (below), we obtained some non-trivial languages. We will put some details here after publishing an online draft. The algorithms for this new languages visit the endmarkers many times. Currently, I have no idea how to prove whether unbounded number of visiting the end-markers is essential for these languages. I did not get the languages you mentioned lastly. Could you please re-write them a bit more formally? – Abuzer Yakaryilmaz Jul 15 '13 at 20:18
  • So I suggested that if the input is $0^n$ where $n=2^km$ where $m$ is an odd number, then this word be in the language if and only if $k$ is odd. – domotorp Jul 16 '13 at 13:25
  • And of course you can create some crazy languages, like for $n$ you start running the $3x+1$, $/2$ algorithm of the Collatz conjecture. Accept the word if you would get a number larger than $n$ during the process and reject it if you reach $1$. Of course, it is an unsolved problem whether the above really halts for all inputs. – domotorp Jul 16 '13 at 13:35
  • 1
    Hm, in fact I think this way I just end up at the same observation what Marzio made already, so nothing new in what I said. I am still interested though in whether we need to read the endmarker more than a bounded number of times. – domotorp Jul 16 '13 at 13:56

2 Answers2

6

This is only an idea that came to my mind while reading Marvin L. Minsky, "Recursive Unsolvability of Post's Problem of Tag and other Topics in Theory of Turing Machines"; in particular the famous theorem Ia:

Theorem Ia: We can represent any partial recursive function $f(n)$ by a program operating on two integers $S_1$ and $S_2$ using instructions $I_j$ of the forms:
(i) ADD 1 to $S_j$, and go to $I_{j_1}$
(ii) SUBTRACT 1 from $S_j$, if $S_j \neq 0$ and go to $I_{j_1}$, otherwise go to $I_{j_2}$
That is, we can construct such a program that starts with $S_1 = 2^n$ and $S_2 = 0$ and eventually stops with $S_1 = 2^{f(n)}$ and $S_2 = 0$

If you have a two way DFA with one counter over a (semi)infinite tape where the input is given in unary: $\$1^{2^n}000...$ then the DFA can:

  1. read the unary input (and store it in the counter);
  2. work on the $0^\infty$ part of the tape and use the distance from the $1$s as the second counter.

so it can simulate a Turing complete two counters machine.

Now, if you have a recursive function $f(n)$ that runs in time $T(n)$ on a standard Turing machine, a two way DFA with one counter that starts on the finite tape $\$1^m\$ \;$ (where $m = 2^n3^{T'(n)}$ and $T'(n) \gg T(n)$) can:

  1. read the unary input (and store it in the counter);
  2. return to leftmost symbol;
  3. divide the counter by 3 until the counter contains $2^n$ in this way: go right looping from states $q_{z_0}, q_{z_1}, q_{z_2}$ and subtracting 1; if counter reaches 0 in state $q_{z_0}$ go to leftmost symbol adding +1 and continue the division loop, otherwise add 1 (if in state $q_{z_1}$) or 2 (if in state $q_{z_2}$) and go to leftmost symbol adding +3 (i.e. recover the previous value of the counter not divisible by 3) and proceed with step 4.;
  4. at this point the counter contains $2^n$;
  5. calculate $2^{f(n)}$ using the $T'(n)$ space available on the right as the second counter (the value of the second counter is the distance from the leftmost symbol $\$$).

So with the special input encoding described above that gives it enough space on the finite tape, a two-way DFA with one counter and unary alphabet can compute every recursive function.

If the approach is correct, it would be interesting to reason about how to choose $T'(n) \gg T(n)$ or when it is enough to pick a large odd $k \gg 2$ and encode the input as $1^m$, $m = 2^n k^n$

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
-1

By non-trivial, I assume you mean a language L that can't be accepted by a 1dca. Here seems to be such a language:

CENTER = { w | w is over {0,1}* and w = x1y for some x, y such that |x| = |y|}

This language can't be accepted by 1dca, but CAN be accepted by 1nca. It can be accepted by a 2dca. Details are left as exercise.

user14004
  • 269
  • 1
  • 2