2
$\begingroup$

I'm currently reading Sipser's Introduction to the Theory of Computation, and I'm reading up about linear bounded automata, now we know from Rice's Theorem that whether a TM can accept all strings in a given alphabet is undecidable, I was wondering if the same could apply to linear bounded automata, if not, how would one go about proving the undecidability of such a problem (or its decidabilty?). Thanks in advance.

$\endgroup$
3
$\begingroup$

For Turing machines another problem is also undecidable: whether it accepts any string at all. This is already undecidable for LBA. Basically the proof is by oberving that we can replace a TM accepting string $w$ by a LBA accepting the `trace of the computation' by the TM on $w$. The verification of the trace of the computation does not need more space than the computation itself, and thus can be verified by a LBA.

The question whether a device accepts all strings is already undecidable on a lower level of the Chomsky hierarchy, the context-free languages (CF grammars,or pushdown automata).

$\endgroup$
2
  • $\begingroup$ But could I prove this undecidability of an LBA accepting all strings using a reduction from the acceptance problem of a TM for example? $\endgroup$ Mar 18 '16 at 21:14
  • $\begingroup$ This can probably be done. Just make sure that all strings that do not code `traces of computations' of the original TM are accepted by the LBA. Returning on what I said, the non-computations together with the non-accepting computations are actually context-free. $\endgroup$ Mar 18 '16 at 22:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.