Decidability of prefix language 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?
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.