Suppose that $L$ is a language recognized by a linear-bounded automaton with the constraint that it can only change each of its input cells at most $t$ times each, where $t$ is some constant integer. Must $L$ belong to $P$, the class of languages decidable in polynomial time? Even more stringently, does there exist a deterministic decider for $L$ that runs in $O(n)$ time, where $n$ is the size of the input? Of course, if we can answer the second question in the affirmative, then we can answer the first question as well.

One approach I'm considering to answering the first question is looking at the length-increasing grammar associated with $L$, and devising an algorithm that checks if this grammar is capable of generating its input in polynomial time.

I'm not sure how to approach the second question. Of course, the tape head for the constrained LBA is writing at worst $O(n)$ times for any input, but the computation on the input still may involve transitions that don't write to the tape.

  • $\begingroup$ Have you tried thinking about the special case $t=0$? $t=1$? Can you solve the question for those? What's the smallest $t$ for which you don't know how to handle it? $\endgroup$ – D.W. Apr 2 '17 at 2:29
  • $\begingroup$ I think in the case of $t = 0$ I can prove that $L$ must be regular. I'm not sure how to treat $t = 1$, though. I suspect that for $t$ sufficiently large, the machine will be powerful enough to recognize certain context-free languages. $\endgroup$ – L.Yi Apr 2 '17 at 3:43
  • 1
    $\begingroup$ For $t=1$, can you find a polynomial-time algorithm to recognize the language? Hint: maybe you can use your result for $t=0$, twice... Hint: Would it help if you knew the location on the tape that was going to be written? $\endgroup$ – D.W. Apr 2 '17 at 6:39
  • $\begingroup$ For $t=2$ you can do all context-free languages, isn't it? Start with Chomsky normal form, and work in reverse. $\endgroup$ – Hendrik Jan Apr 2 '17 at 10:15
  • $\begingroup$ Turing machines that visit each tape cell a bounded number of times are known as Hennie machines, but may rewrite nevertheless. They do accept regular languages. $\endgroup$ – Hendrik Jan Apr 2 '17 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.