# A computable language with a non-computable language that is prefix-free

We say that a language $$L$$ is prefix-free if for every word $$s\in L$$ there does not exist a nonempty string $$w\in\Sigma^*$$ such that $$sw\in L$$ (i.e. no word in the language is a prefix of some other word in the language). For any given language there is a smallest prefix-free sub-language constructed by finding any two words $$s,t\in L$$ such that $$s$$ is a prefix of $$t$$, and removing $$t$$ from $$L$$.

Question: Is there a computable language such that its smallest prefix-free sub-language is not computable?

My attempt: I started trying to think of computable languages where "deciding" whether, for any string that is accepted, there exists a longer string which is also accepted, takes infinite time to check. None of the simple examples that come to mind work: If you take for instance any language which accepts finitely many strings, then it and its prefix-free sublanguage are computable. If you take the language of strings that ends in a 1, it and its sublanguage are computable because every string you could accept is a prefix to another accepting string so the sublanguage would be empty.

After trying to come up with simple examples I started thinking maybe I need to work in reverse, and think of a noncomputable language which is the prefix-free sublanguage of a computable language. The obvious language to pick here is the language of machine-input pairs such that the given machine halts on the given input. But I don't see how I could construe this as the prefix-free sublanguage of some other larger computable language. And I've thought a little about a few other noncomputable languages but that hasn't helped at all.

Suppose language $$L$$ is computable. That is, we can list all words in $$L$$ in nondecreasing length. Scanning the list, we will keep only the words that are not an expansion of any word that have been scanned. The list of words left, $$P$$, is the smallest prefix-free sub-language of $$L$$. Note that they are also in nondecreasing length. So $$P$$ is also computable.
• I think the answer should be that it is possible. Perhaps I've made a mistake in translation but I am told this related fact: Let $f:\Sigma^*\to \{0,1\}$ be any function and define $Prefree(f)$ to be the function $Prefree(f)(x) = 1$ if and only if $f(x)=1$ and there is no $w\in\Sigma^*$ such that $f(xw)=1$. I am told that there is a computable function $f$ such that $Prefree(f)$ is not computable. I can't come up with an example like that either. I believe this is basically a re-characterization of the same problem but perhaps I'm mistaken. Oct 24, 2021 at 19:38