Reductions and contradiction

Reductions and contradiction

danielam 15 May 2010 10:47

Hello
When proving in class that REGtm or EMPTYtm are undecidable , we formalized a reduction from ATM to REGtm or EMPTYtm.
The main idea was to assume there is a TM R that decides REGtm or EMPTYtm and using R to construct a TM that decides ATM and get a contradiction
The logic structure we learned in recitation for building a reduction was to come up with a good reduction from ATM to EMPTYtm and because ATM is undecidable, so is EMPTYtm
My question is how does the contradiction helps us in this case ? I mean that I don't understand the combination of contradiction and reduction in the same proof- is'nt one of these two enough for proving decidability ?

Thank you

Re: Reductions and contradiction

Jonathancito 15 May 2010 12:43

Indeed one of the two suffices. Let's try to state everything.

In class you spoke of reductions: to prove that a language B is not decidable show that given a TM that decides B you can decide a language A which you already know is not decidable (like Atm). A contradiction.

In recitations (and also class) we spoke of mapping reductions, which take advantage of the following theorem:
Theorem: given two languages A and B, if $A \notin R/RE/coRE$ and $A \leq_m B$ then $B \notin R/RE/coRE$, respectively.
So as you can see there is no use of a contradiction here (but there is in the proof of the theorem!) and notice that it is stronger! it applies to R/RE/coRE.

Re: Reductions and contradiction

danielam 15 May 2010 15:47

Great
Thank you