142 views

I have a doubt while understanding step 2 in proof of Rice's Theorem-

According to my understanding,proof of Rice's theorem as follows ( Please suggest If something is wrong in my understanding)

 P is a property of languages of TM which is non-trivial and semantic. We have to prove  Lp={| L(M) is element of P} is un-decidable Proof: Show that $A_{TM} \leq_{m} L_{P}$ Step 1 :There are Turing  machines M1 and M2  L(M1) is element of P and L(M2) is not element of P(P is non trivial) Step 2: Construct a TM M' : M' takes input as M' simulates  TM  M on string w if M accepts w then return else return Step 3: Mp (A decider which decides that given has property P or not)  takes input as  or if Mp accepts then accept else reject

Step 2 says , we can construct a Turing Machine M' which simulate M on w and If M accepts w or reject w take the decision and feed input to the hypothetical decider. But how does M' decides if w is accepted by M or not since M can be looping forever and may not halt at all(Same problem as ATM). Can M' take decision in finite time.

Please give me some insights to I can understand this point.

edited | 142 views
0

ATM m LP

0
$A_{TM}$ is reducible to $L_p$ or $L_p$ is as hard as $A_{TM}$.
0

It is the reduction used in proof by contradiction. If we assume Lp is decidable and reduce ATM to Lp then ATM will be decidable(a contradiction).hence Lp will be undecidable