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?
3
-
$\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 RicherbyCommented Mar 14, 2017 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.Commented Mar 14, 2017 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 RicherbyCommented Mar 14, 2017 at 13:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
answered Mar 14, 2017 at 7:41
-
$\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.Commented Mar 14, 2017 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$ Commented Mar 14, 2017 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.Commented Mar 14, 2017 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$ Commented Mar 14, 2017 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.Commented Mar 14, 2017 at 8:04