2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This problem is so common that it can be considered in public domain. $\endgroup$
    – John L.
    May 16 at 19:03
  • $\begingroup$ @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. $\endgroup$
    – Mohamad S.
    May 16 at 19:07
  • $\begingroup$ By "public domain", I meant there is no need to credit to the source. $\endgroup$
    – John L.
    May 16 at 20:19

1 Answer 1

3
$\begingroup$

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.

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

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.