# Tag Info

10

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

6

Yes. Consider the language $L = \{ a^n \mid n = 2^s, s \geq 0 \}$ and construct a one-way alternating one-counter automaton recognizing $L$ in the following way. First, the automaton starts increasing the value of the counter and guesses when to stop, that is, guesses some value $m$. Then it branches universally: the first branch checks that the length of ...

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

5

A two-way deterministic (nondeterministic) multi-head finite automaton can be simulated by a logspace DTM (NTM), and vice versa. So, for including class $\mathsf{NL}$, you do not need a counter! The value of the counter belonging to a two-way nondeterministic multi-head finite automaton with one-counter can be bounded by a polynomial, otherwise, the ...

4

No, that is not possible. There are languages accepted with $\varepsilon$-transitions that cannot be accepted if $\varepsilon$-transitions can only occur at the end (even if you allow nondeterminism in exchange for restricted $\varepsilon$ usage). Take, for example, the language $L=\{w\#w \mid w\in\{a,b\}^*\}$. As a recursively enumerable language, it can ...

4

I realized that in Fischer, Meyer, and Rosenberg (1968) Theorem 1.3, it is proven that "The language of marked palindrome is not recognizable by any one-way $k-CM$ which operates in time less than $T(n) = 2^{(n/2k)}$." The same result also appears in Petersen (2009).

3

DCM is not closed under reversal. I don't know of a reference, but it is easy to show it using the expressveness lemmata of Chiniforooshan, E., Daley, M., Ibarra, O.H., Kari, L., Seki, S.: One-reversal counter machines and multihead automata: revisited. In particular, they state that for any DCM language $L$, there is a word $w$ such that $L \cap w\Sigma^*$...

2

It doesn't seem to be possible and the reason looks simple (but I might overlook details). After reading $w$ the number of reachable configurations of a real-time automaton is a polynomial in the lenght of $w$, whereas the number of different strings $w$ is exponential.

2

Claim: $S\subseteq NEXP$. To prove it, take $L\in S$. It follows that there exists a machine $K$ s.t. $L=S(K)$. I imagine $K$ to be a Turing machine because I am more familiar with them. Now $n\in L$ iff there exists some computation of $K$ on empty input of length $n$. So we can verify whether $n\in L$ by non-deterministically guessing first $n$ steps of \$...

Only top voted, non community-wiki answers of a minimum length are eligible