Reducing recursive languages - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-11-11T23:01:37Z https://cs.stackexchange.com/feeds/question/7101 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/7101 2 Reducing recursive languages Jernej https://cs.stackexchange.com/users/3092 2012-12-02T08:21:03Z 2012-12-02T18:41:47Z <p>I need a clarification related to the following situation.</p> <p>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.$$</p> <p>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.$</p> <p>What now confuses me is the following.</p> <blockquote> <p>Are there any restrictions on $f$ for this ''reduction'' to work?</p> </blockquote> <p>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.</p> <p>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.</p> https://cs.stackexchange.com/questions/7101/-/7103#7103 3 Answer by Hendrik Jan for Reducing recursive languages Hendrik Jan https://cs.stackexchange.com/users/4287 2012-12-02T10:30:24Z 2012-12-02T10:30:24Z <p>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'. </p> <p>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.</p> https://cs.stackexchange.com/questions/7101/-/7107#7107 4 Answer by Andrej Bauer for Reducing recursive languages Andrej Bauer https://cs.stackexchange.com/users/1329 2012-12-02T18:41:47Z 2012-12-02T18:41:47Z <p>Reductions are about translating one problem to another. In our case, we <em>reduce</em> 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$.</p> <p>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.</p> <p>Allowing $f$ to be partial might make sense when we are interested in <em>semi</em>-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.</p>