1,669 views

2 Answers

Best answer
4 4 votes

We know there is a well known reduction theorem :

If  B is decidable and  there is a mapping reduction  A <m  B , then A is also decidable..

But here A is nothing but manifestation of membership property of RE languages which is not a decidable property(language)..

So if we write the above theorem in implication form :

(If B is decidable) & ( A <m B ) holds  ==>  A is also decidable..

Now as it is clear RHS of implication is already false..

Hence to make the whole implication true , we need to have LHS as false as well as we know  True ==> False will lead to false only which will be invalidation of theorem which is not acceptable..

So in left part , B being decidable is true as it is regular..So compulsorily  A  <m B need to be false bcoz then only LHS will be false which will make implication true..

Hence A is not mapping reducible to B.. 

• selected by
0 0 votes

Assumption: Encoding of Turing Machine M and input string w <M,w> is done using the alphabets which belong to $\Sigma$

Consider a computable function $f:\Sigma^* \to \Sigma^*$ defined as follows
$$f(x) = \{x^R | x \ \epsilon \ \Sigma^* \& \ x^R is \ string \ reverse \ operation \}$$
Certainly if $x \ \epsilon \ \Sigma^*$ then $f(x) \ \epsilon \ \Sigma^* $.

Now, for all valid encodings of the form $<M,w>$ which belong to language A, it is evident that $<M,w>^R$ belong to $\Sigma^*$. Therefore

$$<M,w> \epsilon \ A \to f(<M,w>) \ \epsilon \ B$$

Thus A is mapping reducible to B


This reasoning I gave was wrong, and I thank @Habibkhan for pointing that out. Here I'm still keeping this answer for other as a reference to avoid such mistakes.

Here is the mistake in my reasoning. The condition of mapping reducible is biconditional. So yes, if $<M,w> \epsilon \ A$ is true the RHS will certainly be true. But the implication other way round will not hold true, always.

However, this still cannot be used as a reason to say that $A \nless_m B$. The reasoning offered by @Habibkhan in his answer is in a sense the most appropriate way of doing it.

• edited by
Position:
Show:

Related questions

0 0 votes
0 0 answers
901
901 views
Sandeep Singh asked Dec 23, 2015
901 views
Let L &le; ML&prime; denote that language L is mapping reducible (many to one reducible) to language L&prime;. Which one of the following is True?If L &le;PL&prime; and L...
0 0 votes
0 0 answers
2.0k
2.0k views
Na462 asked Jan 21, 2019
2,003 views
0 0 votes
1 1 answer
1.2k
1.2k views
Utk asked Jan 4, 2016
1,221 views
If Language L1 is reducible to L2 and L2 reducible to L1, then shouldn't they both be Recursively Enumerable Languages? I am really confused with the option given.Source ...
0 0 votes
0 0 answers
1.4k
1.4k views
Lakshman Bhaiya asked Nov 3, 2018
1,372 views
Let there be two problems $A$ and $B$It has been proved that,$A<B$ i.e. $A$ is polynomially reducible to $B.$This polynomialreduction is carried out in time of $O(n).$The...