World's most popular travel blog for travel bloggers.

# many one reduable

, ,
Problem Detail:

I A many one reducable to B and given A is decidable then is B decidable ?

preparing for an exam and please let me know if this holds

I understood how if B is decidable then A is decidable

and if A is not decidable then B is not decidable

###### Answered By : Rick Decker

If $A$ is reducible to $B$ and $A$ is decidable, then $B$ is not necessarily decidable.

Suppose, for example that $A=\{1\}$ and $B$ is, say, $\{\langle\, B\,\rangle\mid L(M)\text{ is infinite}\}$. It's well-known that $B$ is undecidable and of course $A$ is decidable (any finite language is decidable).

Now let $X$ be a TM for which $L(X)=\Sigma^*$. We could pick $X$ to be a one-state TM where the start state was also an accepting state and on every input symbol there was a transition from the start state to itself, for example. In a similar way, let $Y$ be a particular TM for which $L(Y)=\varnothing$.

We could then produce a many-one map from $A$ to $B$ by: $$f(w)=\begin{cases} \langle\, X\,\rangle & \text{if w=1}\\ \langle\, Y\,\rangle & \text{if w\ne 1} \end{cases}$$ Clearly this is a computable function and $w\in A\Longleftrightarrow f(w)\in B$, establishing a reduction from $A$ to $B$ with $A$ decidable and $B$ undecidable.

Best Answer from StackOverflow

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

3200 people like this