Log In

Recent questions tagged rice-theorem

3 votes
1 answer
What is the difference between Non-trivial property (in 1st theorem)and Non-monotonic property ( in 2nd theorem)? I was going through Rice's theorem but unable to differentiate between these 2 properties.Please give the detail to differentiate both For a property to be non-trivial, there ... holding for the language of other (Tno) and L(Tyes)⊂L(Tno) Source:
asked Dec 26, 2016 in Theory of Computation Prajwal Bhat 539 views
3 votes
1 answer
L={⟨M⟩|TM accepts exactly 154 strings} -------------------------------------------------------------------------------------------------------- this language is not decidable but is this R.E?? by second rice theorem, Tyes ={154 strings} and Tno = more than 154 strings hence, Tyes is subset of,it is not even R.E. am i right? please correct me.
asked Dec 16, 2016 in Theory of Computation Akriti sood 381 views
8 votes
2 answers
$L=\left \{ <TM> | TM\ halts\ on\ every\ input\ \right \}$ is above language Recursively enumerable or non recursively enumerable??
asked Dec 16, 2016 in Theory of Computation Akriti sood 2.6k views
2 votes
0 answers
I read this blog and I have a doubt in the first property. An example in this blog is L(M) = {0} and it's written that TMno =sigma* . My doubt is how can it be sigma* as sigma* can also contain {0} which should be accepted by TM.
asked Nov 25, 2016 in Theory of Computation Xylene 216 views
3 votes
1 answer
s Rice theorem says any non-trivial property of a language is Undecidable. Then how is above one REL. Does it mean we cannot say anything for a trivial property?
asked Nov 17, 2016 in Theory of Computation thor 881 views
2 votes
1 answer
Consider the following Languages: $L_{ne}=\{\langle M \rangle \mid L(M)\neq \phi \}$ $L_{e}=\{\langle M \rangle \ \mid L(M)=\phi \}$ where $\langle M \rangle$ denotes encoding of a Turing Machine $M$ Then which of the following is true? (a) $L_{ne}$ ... r.e. (b) Both are not r.e. (c) Both are recursive (d) $L_{e}$ is r.e. but not recursive and $L_{ne}$ is not r.e.
asked Dec 15, 2015 in Theory of Computation Rajat Sharma 1 877 views