Mapping Reducible

Question

A={<M,w> M is a TM that accepts w}

B=Ʃ^*

Is A Mapping reducible to B?

http://theory.stanford.edu/~trevisan/cs154-12/reductions3.pdf

Answer 1

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.. 

Comments

The explanation could not have been more better than this :)

But, sir one thing is not clear to me in below answer you have mentioned that there is some close relation with RE but not REC languages , which relation I could not get this.

----------------------------------------------------------------------------------------------------------------------------------------------------------

A different doubt:

Is Membership in RE is same as halting problem of RE ? ( and hence Undecidable i.e. RE but not REC )

---

I told that with regard to reduction properties of various language families..

And yes membership in RE is same as halting problem of RE ( and hence undecidable but specifically semi decidable i.e. RE but not REC )..

Answer 2

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.

Comments

Ur answer is not generalalistic to all Turing machines..There are languages which are RE but not REC bt they are represented by Turing Machine..

---

Sorry but I could not get your point. Yes there are languages that are RE but not REC. But what impact do they have on this?

---

There is a close relation to this..Plz try to check my explanation..