Problem Detail: At the midterm there was a variant of the following question:
For a decidable $L$ define $$text{Pref}(L) = { x mid exists y text{ s.t. } xy in L}$$ Show that $text{Pref}(L)$ is not necessarily decidable.
But if I choose $L=Sigma^*$ then I think $text{Pref}(L)$ is also $Sigma^*$, thus decidable. Also $L=emptyset$ gives the same result. And since $L$ must be decidable I cannot pick the halting problem or such..
- How can I find $L$ such the $text{Pref}(L)$ is not decidable?
- Which conditions on $L$ will make $text{Pref}(L)$ decidable, and which will make it undecidable?
Asked By : Ran G.
Answered By : Kaveh
Note that using an existential quantifier in front of a decidable language we can obtain any r.e. language, i.e. every r.e. language is expressible as $$ { xin Sigma^* mid exists y in Sigma^* langle x,y rangle in V } $$ where $V$ is a decidable language. These include undecidable r.e. languages like $$A_{TM} = { langle e, xrangle mid text{$e$ encodes a Turing machine which accepts $x$} }$$. The only difference here is that here we have to separate $x$ and $y$ ourselves. The standard trick is to use a new symbol to separate the two parts (assume that the separator belongs to $y$). Therefore any r.e. language including undecidable ones can be expressed in this format. For the second question, there is no general algorithmic way to check if the prefixes of a given decidable language is undecidable. This follows from Rice’s theorem.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/285
