Decidability of prefix language

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..

1. How can I find $L$ such the $\text{Pref}(L)$ is not decidable?
2. 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

$$ \{ x\in \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, x\rangle\ \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