Let $f:\Sigma^{*}\to\Sigma^{*}$ be a computable function and let $L$ be a recursive language. Is $f(L):=\left \{{f(w)|w\in L} \right\}$ recursive?

Here, I see clearly, that $f^{-1}(L)$ is recursive (simply by applying $f$ on an input $w$, and then see if $f(w)$ belongs to $L$).

My intuition tells me that $f(L)$ should also be recursive. For an input $w$, we should verify if there exists $x\in \Sigma^{*}$ such that $f(x)=w$. We can apply $f$ on every word lexicographically. Surely, if $w\in f(L)$, the machine accepts. But otherwise, the machine does not halt. So maybe my intuition is wrong?


Inspired by this question, I have come up with the following.

Assume that $\langle\cdot\rangle$ is an encoding for TM's, for which the encoding of one Turing machine is never a prefix of the encoding of another.

Let $f$ be defined as the identity on an input which does not contain a TM enconding as a prefix. If the input contains such a prefix, $f$ returns this prefix.

$f$ is computable and it is well defined due to the encoding property.

Let $L=\left\{ \langle M\rangle n \mid \text{$M$ halts on the empty input after $n$ steps} \right\}$.

Then $L$ is recursive but $f(L)=\left\{ \langle M\rangle \mid \text{ $M$ halts on the blank tape} \right\}$ which is not recursive.

| cite | improve this answer | |

Here's an approach to this problem that doesn't involve imagination. $\{f(w) \mid w \in L\}$ is strongly reminiscent of the definition of a recursively enumerable set — specifically, a non-empty set $S$ is r.e. iff there exists some function $f$ such that $S = f(\Sigma^*)$. If $f(L)$ was recursive for all total recursive $f$ and recursive $L$, it would mean that all r.e. sets would be recursive.

So let $S$ be a subset of $\Sigma^*$ that is recursively enumerable but not recursive, e.g. the set of encodings of halting Turing machines. Its enumeration function $f$ is a total recursive function with the property that $f(\Sigma^*)$ is not recursive even though $\Sigma^*$ is.

| cite | improve this answer | |
  • $\begingroup$ What do you mean by an enumeration function? $\endgroup$ – Yoav bar sinai Aug 19 '14 at 12:15
  • 3
    $\begingroup$ @Yoavbarsinai This comes from the definition of a recursively enumerable set: it's a set which is the image of $\Sigma^*$ (or $\mathbb{N}$, whatever you pick as the starting space) under a computable function. If $S$ is r.e., then any computable function such that $S = f(\Sigma^*)$ is called an enumeration function for that set. $\endgroup$ – Gilles 'SO- stop being evil' Aug 19 '14 at 12:39

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.