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

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.

• This problem is so common that it can be considered in public domain. May 16 at 19:03
• @JohnL. I know but I didn't really find a good and simple answer so I designed my own one and I wanted to check if it's right. May 16 at 19:07
• By "public domain", I meant there is no need to credit to the source. May 16 at 20:19

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.

• Thanks a lot for your comment and notes on my answer, I'll try to follow it in the questions I'm solving. May 17 at 12:18
• I think one should point out that to make this work smoothly, an suitable coding for $\langle , , \rangle$ needs to be chosen.
– Arno
May 23 at 10:31