Disprove: if L is decidable then Prefix(L) is decidable

Question

The following question was sent to me by a friend and I didn't really ask him about its source so I couldn't provide the source of it. I solved the question and I need to ensure my answer not just for him but also for myself since it's important to me too.

Question: Prove or Disprove: if $L$ is a decidable language, so is $\text{Prefix}(L)$.

My Answer: I think that the claim is wrong. I used the language:

$$L=\{\langle M,x,t\rangle\ |\ M\text{ halts on }x\text{ within }t\text{ steps}\}$$

It's clear that $L$ is decidable. I assume by contradiction that $\text{Prefix}(L)$ is decidable also.

Claim: $\text{Prefix}(L)$ is decideable $\iff \text{HALT}$ is decidable.

$(\Longrightarrow)$: Let $\langle M,x,t\rangle\in L$ so $M$ halts on $x$ within $t$ steps therefore $\langle M,x\rangle\in \text{HALT}$.

$(\Longleftarrow)$: Let $\langle M,x\rangle\in \text{HALT}$ so $M$ halts on $x$ within finite number of steps, let's call this number $t$, therefore $\langle M,x,t\rangle\in \text{Prefix}(L)$.

Conclusion: if $\text{Prefix}(L)$ is decidable then the $\text{HALT}$ problem is decidable too, which is known to be wrong. QED.

Answer 1

It is correct that if $L$ is decidable language $\text{Prefix}(L)$ can be undecidable. The language $L$ given in the question is a concise example of a decidable language the prefix language of which is undecidable.

---

However, your proof is somewhat specious.

Firstly, in order to show $\text{Prefix}(L)$ is undecidable, all you need to show is $$\text{Prefix}(L) \text{ is decideable}\Longrightarrow\text{HALT} \text{ is decidable}.$$ There is no need to show the other direction, "$\Longleftarrow$". This is a minor issue, since it does not matter much when you have done unnecessary work.

Secondly, the way you prove "$\Longrightarrow$" does not make much sense to me. What you want to show that if we can decide (the membership problem of) $L$, then we can also decide (the membership problem of) $\text{HALT}$. The following is a correct proof of "$\Longrightarrow$".

Suppose we are given a Turing machine $T$ and a word $w$.

• If $\langle T, w\rangle\in \text{Prefix}(L)$, then there is a $t$ such that $\langle T, w, t\rangle\in L$, which means $T$ halts on word $w$.
• Otherwise, $\langle T, w\rangle\not\in \text{Prefix}(L)$, then there is no $t$ such that $\langle T, w, t\rangle\in L$, which means $T$ does not halt on word $w$.

Hence, if we can decide whether $\langle T, w\rangle\in \text{Prefix}(L)$, we can decide whether $\langle T, w\rangle\in \text{HALT}$.

---

Exercise: Given an oracle that can decide $\text{HALT}$, $\text{Prefix}(L)$ is still not decidable. Here $L$ is specified in the question.

The exercise above means that the proof for the direction "$\Longleftarrow$" in the question is specious.