# computability - decidability of a prefix language

For any language $L$ over $\{0,1\}^*$, a language $L'$ can be defined as $\{ a | ab \in L \text{ for some } b \in \{0,1\}^* \}$.

If $L$ is decidable, is $L'$ decidable?

I think that $L'$ should be decidable because we can create a Turing machine for $L'$ that will run the decider for $L$ on the input $w$ for $L'$, accept if it accepts, and otherwise will enumerate all the possible strings $b$ and run $wb$ on $L$. Does that make sense?

• How do you check if w is not in L'? There are infinitely many possible suffixes (in general case). – Karolis Juodelė Feb 20 '13 at 19:10
• Hmm, I guess I can't do that then. If that's the case, it should be undecidable and I should be able to reduce some undecidable problem to it right? – Jay Feb 20 '13 at 20:33

Pick some self-terminating encoding of Turing machines. (That means that the encoding of one Turing machine is never a prefix of the encoding of another.) Consider the language $L$ consisting of strings $Mn$, where $M$ is an encoded Turing machine, $n$ is interpreted as a number, and $M$ halts within $n$ steps (on the empty input).
• In my example $L$ is decidable but $L'$ is not. – Yuval Filmus Feb 20 '13 at 21:35