2
$\begingroup$

A linear bounded automaton (LBA) is a restricted TM with finite tape.

Let $A_{LBA} = \{\langle M, w \rangle | M$ is an LBA that accepts string $w \}$. It can be shown that $A_{LBA}$ is decidable: since an LBA has only finite number of configurations, therefore an LBA does not halt iff it cycles. A cycling in the computation history of LBA can be detected.

Let $E_{LBA} = \{\langle M \rangle | M$ is an LBA such that $L(M) = \emptyset \}$. Sipser (Theorem 5.10) proved that $E_{LBA}$ is not decidable.

Here is where my question arises: since an LBA has finite space on the tape and its input alphabet is finite, the number of possible input string must be finite. Why can we not just enumerate every input $w$ and check if LBA accepts $w$? What am I missing?

$\endgroup$

1 Answer 1

2
$\begingroup$

I suspect the word "finite" is confusing you. Every integer is "finite", yet the set of all possible integers is not finite, and there is no finite number that is an upper bound on all possible integers. Or maybe it is the order of quantifiers.

For any fixed string $w$, there is a number $n$ (which depends on $w$) we can compute, so that the LBA has at most $n$ states.

However, there is no single number $n$ that works for all $w$. The longer the string $w$ is, the larger you need to make $n$.

That is what is wrong with your reasoning in the last paragraph of your question. There is no single number $N$ that is an upper bound on the number of states, that works for every input string $w$. And, it's not possible to enumerate every input $w$, because there are infinitely many possible strings $w$, so such a procedure might never halt.

$\endgroup$
3
  • $\begingroup$ it's not possible to enumerate every input $w$, because there are infinitely many possible strings $w$, so such a procedure might never halt. I have a question considering this statement: If we know a LBA's tape has $t$ cells and also this LBA's input alphabet has $a$ elements, there could be be at most $a^t$ input $w$, couldn't it? $\endgroup$ Dec 31, 2021 at 9:14
  • $\begingroup$ @LongPollehn, sure, but we don't know that, when trying to decide $E_{LBA}$. $\endgroup$
    – D.W.
    Jan 1, 2022 at 5:16
  • $\begingroup$ To decide $E_{LBA}$, your algorithm has to work on inputs $w$ of every possible length. So there is no upper bound on the length of the input $w$ that you can assume. $\endgroup$
    – D.W.
    Jan 1, 2022 at 6:43

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.