9
$\begingroup$

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?
$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ can you explicitly give the $V$ that creates $A_{TM}$? $\endgroup$ – Ran G. Mar 13 '12 at 4:33
  • 2
    $\begingroup$ let the $y$ be a string intended to represent a halting accepting computation of $M_e$ on $x$, $V$ will check if $y$ is an accepting computation of $M_e$ on $x$. $\endgroup$ – Kaveh Mar 13 '12 at 4:41
  • $\begingroup$ That's a nice solution! $\endgroup$ – Ran G. Mar 13 '12 at 6:03
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.