[Solved]: Reducing recursive languages

Problem Detail: 

I need a clarification related to the following situation.

Consider a Turing machine $T_1$ that halts for every input. In other words $J_1 = L(T_1) \subseteq \Sigma^*$ is recursive. Suppose we are given a function $f:\Sigma^* \mapsto \Sigma^*$ and a language $J_2 \in \Sigma^*$ such that $$ x \in J_2 \iff f(x) \in J_1.$$

I would assume this readily implies $J_2$ is recursive as well since one can create a Turing machine $T_2$ that on given input $x$ evaluates $y = f(x)$ and simulates $T_2$ on the given input $y.$ Clearly $L(T_2) = J_2.$

What now confuses me is the following.

Are there any restrictions on $f$ for this ''reduction'' to work?

What is the usual approach here? Is $f$ assumed to be given as a black box that always evaluates $f(x)?$ If so could someone explain the motivation behind this, because it appears to me that it could as well be that $f(x)$ cannot be computed effectively and hence $T_2$ cannot be constructed in a "feasible" way.

As for the motivation for the question, I would like to show that given $f:\Sigma^* \mapsto \Sigma^*$ and a recursive language $L,$ the language $f^{-1}(L)$ is recursive as well.

Asked By : Jernej

Answered By : Andrej Bauer

Reductions are about translating one problem to another. In our case, we reduce the question "$x \in J_2$" to the question "$f(x) \in J_1$". Naturally, for this to make any sense $f$ has to be computable (otherwise we can reduce anything to anything). But it is also important to pay attention to the totality of $f$.

We normally require that $f$ be total because we do not want to be in a position when the reduction itself never ends. In this case, if $f$ is computable and total, and $J_1$ is computable, then $J_2 = f^{-1}(J_1)$ is computable as well.

Allowing $f$ to be partial might make sense when we are interested in semi-deciding whether $x \in J_2$ because then we might as well allow $f(x)$ to diverge when $x \not\in J_2$. But this is not usualy done.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents