2
$\begingroup$

The halting problem and therefore the acceptance problem are decidable for LBAs, but are the infinite extensions of these problems decidable?

Given a LBA, can you decide whether there exists an input on which the LBA halts? Given a LBA, can you decide whether the LBA accepts a certain non-empty, non-finite language?

$\endgroup$

1 Answer 1

1
$\begingroup$

Given a Turing machine $M$, you can construct an LBA $A$ that given as input a word of length $n$, it simulates $M$ on the empty tape as long as $M$ uses up to $n$ space, and the moment $M$ exceeds space $n$, it enters an infinite loop. In contrast, if $M$ ever halts, then $A$ also halts. Thus $A$ halts on some input iff $M$ halts on the empty input.

You can try to show that the second property is undecidable using a similar argument.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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