• edited by
825 views
0 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: 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.

Please log in or register to answer this question.

Position:
Show:

Related questions

1 1 vote
0 0 answers
694
694 views
Sumaiya23 asked Jan 23, 2018
694 views
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.
1 1 vote
1 1 answer
2.5k
2.5k views
rahul sharma 5 asked Aug 5, 2017
2,485 views
L = {M|M is a TM that accepts all even numbers}For the above language i can have Tyes machine which has all even numbers.And Tno as machine whose language is empty.So i c...
0 0 votes
1 1 answer
1.3k
1.3k views
Salazar asked Oct 28, 2017
1,250 views
Example# 3 from Part-1 Rice's Theorem from https://gatecse.in/rices-theorem/ states as follows (3) L(M) is recognized by a TM having even number of statesSol: This is a t...
5 5 votes
1 answers 1 answer
2.4k
2.4k views
Lucky sunda asked Jan 3, 2017
2,371 views
I am unable to understand when to apply Rice's theorem and when to not. How L2 is decidable.