[Solved]: The image of a recursive language under a computable function

Problem Detail: 

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?

Asked By : Yoav bar sinai

Answered By : Yoav bar sinai

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29041

3.2K people like this

 Download Related Notes/Documents