The image of a recursive language under a computable function

Question

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?

Answer 1

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.

Answer 2

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.