2
$\begingroup$

I am a little bit confused about the emptiness problem of the linear bounded automaton (LBA). I know that this problem is undecidable. However if we assume that is decidable, what could be wrong if we reduce it to the acceptance problem of LBA?

$\endgroup$
  • $\begingroup$ I'm not sure what you're trying to do. You don't need to assume that something is decidable before reducing it to something else. But, if you come up with a reduction from a problem A to a decidable problem B, you know that A is decidable; if you reduce an undecidable problem C to a problem D, you know that D is also undecidable. $\endgroup$ – David Richerby Mar 14 '17 at 9:02
  • $\begingroup$ It seems I put it the other way, what I want to do is to reduce the acceptance problem of LBA to the emptiness problem of LBA giving that the acceptance problem is decidable and assuming that we have no idea whether the emptiness problem is decidable or not. The question is why we cannot do this? And if there is a way to do it then how? $\endgroup$ – O.S. Mar 14 '17 at 9:08
  • $\begingroup$ Reducing a problem to another is a way of proving that one of the problems is or is not decidable. If you were to assume decidability in advance, you'd be assuming the thing you were trying to prove. $\endgroup$ – David Richerby Mar 14 '17 at 13:00
1
$\begingroup$

Since the acceptance problem for LBAs is decidable, if you could reduce th emptiness problem to the acceptance problem, then the emptiness problem for LBAs would be decidable. However, the emptiness problem for LBAs is not decidable. This shows that we cannot reduce the emptiness problem to the acceptance problem.

It seems that you are confused about the direction of the reduction. When reducing problem A to B, we show how to solve problem A using problem B, not the other way around.

$\endgroup$
  • $\begingroup$ Thanks for the feedback. But what if we reduce the acceptance problem to the emptiness problem assuming that we have no idea that the emptiness problem of LBA is decidable or not and the only info that we have is the acceptance problem of LBA is decidable. $\endgroup$ – O.S. Mar 14 '17 at 7:51
  • $\begingroup$ Since the acceptance problem is decidable and the emptiness problem is non-trivial, you can reduce the acceptance problem to the emptiness problem. $\endgroup$ – Yuval Filmus Mar 14 '17 at 7:53
  • $\begingroup$ Thanks again. Does this mean that we can use the acceptance problem of LBA (which is decidable) to show that the emptiness problem of LBA is undecidable? Any general view of how we can do this? $\endgroup$ – O.S. Mar 14 '17 at 7:58
  • $\begingroup$ I don't see how you would do that. Perhaps you should ask a different question in which you explain your real question instead of hiding it. $\endgroup$ – Yuval Filmus Mar 14 '17 at 7:59
  • $\begingroup$ I am new to the concept of the reducibility. Your first answer has helped me to rephrase my question in a better way. Thanks $\endgroup$ – O.S. Mar 14 '17 at 8:04

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.