Let P be a property of the language of a Turing machine. We say P is non-trivial if it fulfills the following 2 conditions: - Some, but not all Turing machines satisfy the property P, and - P is a property of the language of the machines – i.e., if M1 and M2 are two Turing machines and L(M1) =L(M2), then they either both satisfy property P or they both do not satisfy property P. ---------------------------------------------------------------------- Note:AT M,HALTT M, and LCF are all problems related to non-trivialproperties. Rice’s Theorem:LetPbe any non-trivial property of the language of aTuring machine. DefineLPas follows: LP={〈M〉 |M is a Turing machine satisfying property P}. ThenLPis undecidable. ---------------------------------------------------------------------- In this problem, you will prove Rice’s Theorem. You may assume that (i) ifL(M) =∅, then〈M〉/∈LP, and (ii) MP is a Turing machine such that〈MP〉 ∈ LP. (a) Use the two assumptions above to create a machine M2 that sat-isfies P iff M accepts w, where〈M, w〉is the input the ATM. Describe L(M2). (b) Use M2 to prove LP is not decidable by showing ATM reduces to LP.
Let P be a property of the language of a Turing machine. We say P is non-trivial if it fulfills the following 2 conditions:
- Some, but not all Turing machines satisfy the property P, and
- P is a property of the language of the machines – i.e., if M1 and M2 are two Turing machines and L(M1) =L(M2), then they either both satisfy property P or they both do not satisfy property P.
----------------------------------------------------------------------
Note:AT M,HALTT M, and LCF are all problems related to non-trivialproperties.
Rice’s Theorem:LetPbe any non-trivial property of the language of aTuring machine. DefineLPas follows:
LP={〈M〉 |M is a Turing machine satisfying property P}.
ThenLPis undecidable.
----------------------------------------------------------------------
In this problem, you will prove Rice’s Theorem.
You may assume that (i) ifL(M) =∅, then〈M〉/∈LP, and (ii) MP is a Turing machine such that〈MP〉 ∈ LP.
(a) Use the two assumptions above to create a machine M2 that sat-isfies P iff M accepts w, where〈M, w〉is the input the ATM. Describe L(M2).
(b) Use M2 to prove LP is not decidable by showing ATM reduces to LP.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
