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.
Reducing recursive languages
computability;turing machines
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.