EXERCISE 8 For each of the following languages, decide whether Rice\'s theorem a
ID: 3704434 • Letter: E
Question
EXERCISE 8 For each of the following languages, decide whether Rice's theorem applies, and explain why it does or does not. a. Ip | p is a recognition method and L(p) contains the empty string! b. {p l p is a recognition method and UpG ?*) c. Im mencodes a Turing machine M with abba E L(M) d. l p is a recognition method that contains the statement x=1 ; } e. Ip | p is a recognition method that, when run on the empty string, executes the statement x-1; f. mm encodes a Turing machine M for which L(M) is finite]Explanation / Answer
Ans :
(a)
If Turing Machine recognize the empty language L, that does not have the properly p. If it have the property p than the compliment of p according to the rice theorem The un decidability of that complement would immediately imply the un decidability of p. hence it rice theorem applied to take the compliment. { p I p is a recognition method and L(P)contains the empty string}.
(b)
Yes ,it does because A property about Turing machines can he represented as the language of all turing machines, encoded as string ,that satisfy that property.
(c)
Yes it does because the property p is about the language recognized by turing machine if whenever L(M) = L(N ) then P contains (the encoding of) M if it contains (the ending of) N. The property is non-trivial if there is at least one turing machine that has the property and least one that hasn’t.
(d)
No, it does not exist because the compliment of any p is un decidability hence it does not prove that statement x= 1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.