The Gateway to Computer Science Excellence
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


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.

in Theory of Computation by Junior (755 points)
edited by | 142 views

ATM m LP  

Please explain its' meaning?

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

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

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,357 answers
105,256 users