edited by
472 views
0 votes
0 votes

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: M(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.

edited by

Please log in or register to answer this question.

Related questions

1 votes
1 votes
0 answers
1
Sumaiya23 asked Jan 23, 2018
439 views
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.
5 votes
5 votes
1 answer
4
Lucky sunda asked Jan 3, 2017
1,589 views
I am unable to understand when to apply Rice's theorem and when to not. How L2 is decidable.