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.


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.

| cite | improve this answer | |

The answer is already in your question. One must assume that $f$ is effectively computable, i.e., there is a Turing Machine that, given $x$ (on one tape) computes $f(x)$ (on another tape). It should also halt on every input, but that is implicit in 'computes'.

We need this in order to avoid that $f$ indeed computes an undecidable property of $x$; e.g., when $J_1 = \Sigma^*$ and $f:\Sigma^* \to \{0,1\}$ computes the halting problem.

| cite | improve this answer | |
  • $\begingroup$ But assuming the statement of a problem says "given a function $f:\Sigma^* \mapsto \Sigma^*$ shouldn't this imply $f$ is given as a Turing machine that for every input $x$ computes $f(x)$ ? $\endgroup$ – Jernej Dec 2 '12 at 11:31
  • $\begingroup$ If in the same document we cannot assume that any language $L\subseteq \Sigma^*$ is computable/decidable, it would be strange to assume functions are computable by default. Your question explicitly (and emphasized) askes for conditions that make your reasoning work. Computability of $f$ is precisely that condition, and usually it is explicitly stated. $\endgroup$ – Hendrik Jan Dec 2 '12 at 11: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.