Decidability of prefix language

Question

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?

Answer 1

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.

Answer 2

Meta-knowledge: you want to find a non-decidable language which nonetheless has some computational property. An arbitrary non-decidable language is probably not going to lead you very far. But a semi-decidable one…

---

Stronger hint: what's a semi-decidable language? It means we can enumerate the words: it's some set of words $u$ such that there exists an integer $n$ such that

$$u = f(n)$$

Stare at this equation for a bit, with decidability and prefixes in mind.

---

Intuitively speaking, suppose you have some $x$ and you'd like to test whether it's in $\mathrm{Pref}(L)$. You're not going to do better in general than check $x a$, $x b$, $x a a$, etc. where $a,b,\cdots$ are the letters of the alphabet. This is a partial recursive function that tests membership in $\mathrm{Pref}(L)$. Of course, we knew that $\mathrm{Pref}(L)$ was r.e. already; what we need to show is that sometimes there's no alternative method. Let's take some set $S \subset \mathbb{N}$ which is r.e. and not recursive, and let $f$ be an enumeration of $S$ ($S = {f(x) \mid x\in\mathbb{N}}$).

Assume the alphabet contains three symbols $0$, $1$ and $:$ (if you only have two symbols $\{\aleph,\beth\}$, encode $0$ as $\aleph\aleph$, $1$ as $\aleph\beth$ and $:$ as $\beth$). If $n\in\mathbb{N}$, let $\bar n$ be $n$ written in base 2 using the symbols $0$ and $1$ with no leading $0$.

Let $L = \{\bar y\mathord:\bar x \mid y = f(x)\}$. In plain English, we're taking the elements of $S$ and tacking on their enumeration index. $L$ is clearly decidable (check that there is a single $:$, that the two digit sequences contain no leading $0$, and that the first digit sequence spells the image by $f$ of the number that the second one spells). Yet deciding whether some $\bar y$ is a prefix of $L$ is tantamount to deciding whether $y$ is in $S$, which you can't do without knowing $x$ since $S$ is not recursive by assumption. Formally, $\mathrm{Pref}(L)$ is not decidable, because $\mathrm{Pref}(L) \cap \{0,1\}^*\mathord: = S\mathord:$ is not decidable.