Cheap and Secure Web Hosting Provider : See Now

many one reduable

, , No Comments
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

Asked By : Csfunda
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

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback