search
Log In
1 vote
166 views
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.
in Theory of Computation 166 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
226 views
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 ... at all(Same problem as ATM). Can M' take decision in finite time. Please give me some insights to I can understand this point.
asked Dec 15, 2017 in Theory of Computation Durgesh Singh 226 views
1 vote
0 answers
2
372 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 can say it is undecidable. But to show it is Not RE. What should be my Tno,so that ... Tno machine?I am assuming here that the property of the language as "Only all even numbers",i guess the same has been given in the question.
asked Aug 5, 2017 in Theory of Computation rahul sharma 5 372 views
0 votes
0 answers
3
352 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 states Sol: This is a trivial property. This set equals the set of recursively enumerable languages. According to the ... property then? Can someone give me an example for which TYES and TNO cannot be found and let me know if my approach is correct ?
asked Oct 28, 2017 in Theory of Computation Salazar 352 views
4 votes
1 answer
4
504 views
I am unable to understand when to apply Rice's theorem and when to not. How L2 is decidable.
asked Jan 3, 2017 in Theory of Computation Lucky sunda 504 views
...