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={<M>| 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,w> M' simulates TM M on string w if M accepts w then return <M2> else return <M1>
Step 3: Mp (A decider which decides that given<M> has property P or not) takes input as <M1> or <M2> 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.