<p>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:</p>

<blockquote>
<b>Theorem Ia:</b> 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:<br>
(i) ADD 1 to $S_j$, and go to $I_{j_1}$<br>
(ii) SUBTRACT 1 from $S_j$, if $S_j \neq 0$ and go to $I_{j_1}$, otherwise go to $I_{j_2}$<br>
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$
</blockquote>

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

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

<p>so it can simulate a Turing complete two counters machine.</p>

<p>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 <em>finite tape</em> $\$1^m\$ \;$ (where $m = 2^n3^{T'(n)}$ and $T'(n) \gg T(n)$) can:</p>

<ol>
<li>read the unary input (and store it in the counter);</li>
<li>return to leftmost symbol;</li>
<li>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.;</li>
<li>at this point the counter contains $2^n$;</li>
<li>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 $\$$).</li>
</ol>

<p>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.</p>

<p>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$</p>

CC BY-SA 3.0
2013-05-31T18:58:00.523Z
2013-06-02T10:09:50.517Z
2013-06-02T10:09:50.517Z
Marzio De Biasi
<p>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:</p>

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

<p>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.</p>

CC BY-SA 3.0
2013-05-31T19:24:18.033Z
The OP asks for *unary* languages (the input is given as $\$1^n\$$)
Marzio De Biasi
CC BY-SA 3.0
2013-05-31T19:22:46.897Z
2013-05-31T19:22:46.897Z
user14004
<p>2dca's (two-way deterministic one-counter automata) <a href="http://dl.acm.org/citation.cfm?doid=193820.193835">(Petersen, 1994)</a> can recognize the following unary language:
\begin{equation} 
\mathtt{POWER} = \lbrace  0^{2^n} \mid n \geq 0 \rbrace.
\end{equation}</p>

<p>Is there any other nontrivial unary language recognized by 2dca's?</p>

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

<hr>

<p>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.</p>

CC BY-SA 3.0
2012-07-08T20:50:51.207Z
Could you add a link to a definition of a 2DCA ?
Suresh Venkat
CC BY-SA 3.0
2012-07-08T22:00:15.297Z
@SureshVenkat: I added a reference and also a definition.
Abuzer Yakaryilmaz
CC BY-SA 3.0
2013-05-07T17:19:40.903Z
@AbuzerYakaryilmaz: for every fixed $k$ it can recognize $\{0^{k^n} : n \geq 0\}$
Marzio De Biasi
CC BY-SA 3.0
2013-05-08T05:16:08.413Z
@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
CC BY-SA 3.0
2013-05-08T06:50:54.137Z
@AbuzerYakaryilmaz: I thought it might be :-) A curiosity: are you actually/still working on 2DCAs ?
Marzio De Biasi
CC BY-SA 3.0
2013-05-08T08:29:07.040Z
@MarzioDeBiasi: I am interested in quantum generalizations of counter machines. Then, it is natural to examine its their classical counterparts, too.
Abuzer Yakaryilmaz
CC BY-SA 3.0
2013-07-15T08:22:54.003Z
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
CC BY-SA 3.0
2013-07-15T09:57:35.107Z
@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
CC BY-SA 3.0
2013-07-15T12:50:36.760Z
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
CC BY-SA 3.0
2013-07-15T13:30:23.990Z
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
CC BY-SA 3.0
2013-07-15T20:18:46.117Z
@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
CC BY-SA 3.0
2013-07-16T13:25:22.500Z
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
CC BY-SA 3.0
2013-07-16T13:35:07.323Z
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
CC BY-SA 3.0
2013-07-16T13:56:09.943Z
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
CC BY-SA 3.0
2013-06-03T07:08:47.283Z
@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
CC BY-SA 3.0
2013-06-03T12:36:55.207Z
@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
<fl.formal-languages><automata-theory><counter-automata>
Unary languages recognized by two-way deterministic counter automata
Abuzer Yakaryilmaz
# Unary languages recognized by two-way deterministic counter automata

(Asked by: username_0 on 2012-07-08)

2dca's (two-way deterministic one-counter automata) [(Petersen, 1994)](http://dl.acm.org/citation.cfm?doid=193820.193835) 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.

**Tags:** fl.formal-languages, automata-theory, counter-automata

> **Comments:**
> **username_1**: Could you add a link to a definition of a 2DCA ?  
> **username_0**: @SureshVenkat: I added a reference and also a definition.  
> **username_2**: @AbuzerYakaryilmaz: for every fixed $k$ it can recognize $\{0^{k^n} : n \geq 0\}$  
> **username_0**: @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.  
> **username_2**: @AbuzerYakaryilmaz: I thought it might be :-) A curiosity: are you actually/still working on 2DCAs ?  
> **username_0**: @MarzioDeBiasi: I am interested in quantum generalizations of counter machines. Then, it is natural to examine its their classical counterparts, too.  
> **username_2**: @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?  
> **username_0**: @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:)  
> **username_3**: Is there any language that can be recognized by a 2DCA but not by one that halts when it first reads the (right) endmarker?  
> **username_0**: @username_3: 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.  
> **username_3**: 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.  
> **username_3**: 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.)  
> **username_0**: @username_3: 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?  
> **username_3**: 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.  
> **username_3**: 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.  
> **username_3**: 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.  

---

## 2 answers

### Answer by username_2 on 2013-05-31. Score: 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$


---

### Answer by username_4 on 2013-05-31. Score: -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.

> **Comments:**
> **username_2**: The OP asks for *unary* languages (the input is given as $\$1^n\$$)  

---

