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.

StackExchange Computer Science Q#285, answer score: 9