1
$\begingroup$

I know for an LBA the emptiness problem is undecidable. However I am not clear on how to reduce the halting problem of Turing machines to this as LBAs are strictly computationally less powerful than Turing machines. Or should I approach with reductions using computational histories of a Turing machine on an input.

$\endgroup$
  • $\begingroup$ Try a reduction from the halting problem. On an input of length $n$, an LBA can simulate a Turing machine using roughly $n$ space. $\endgroup$ – Yuval Filmus Sep 4 '18 at 5:43
  • 1
    $\begingroup$ @YuvalFilmus My confusion was how can an LBA simulate Turing Machine as turing machines are strictly computationally more powerful than LBAs. Else the reduction is like the standard reductions for undecidability for Turing Machines. $\endgroup$ – Arka Pal Sep 4 '18 at 7:31
  • $\begingroup$ Just as the problem "does the Turing machine $M$ halt within $n$ steps" is decidable despite the halting problem being undecidable, so an LBA can decide whether a Turing machine halts while using at most a given amount of space (encoded in unary). $\endgroup$ – Yuval Filmus Sep 4 '18 at 15:47
  • 1
    $\begingroup$ I suggest taking a look at the proof that the emptiness problem for LBAs is undecidable. $\endgroup$ – Yuval Filmus Sep 4 '18 at 15:47
1
$\begingroup$

Thanks to @YuvalFilmus I managed to reduce the Halting problem to the given problem. We design an LBA B, that given an instance of the Halting problem, $\langle M,x\rangle$, accepts the valid computation histories of M on x. If M doesn't halt on x, $L(B)=\phi$ which is regular. However, if M does halt $L(B)=VAL-COMPS(M,x)$ which is not regular(not even CFL). Techinically, I have reduced the complement of the Halting problem, but as we know that it is also not decidable, so it's fine.

$\endgroup$

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.